BFS for weighted graph

[Chong Wang]

Hi.

I am reviewing the BFS for weighted graph. I understand we should use a priority Queue to implement it, but i have a question: does BFS always return the shortest path? 

for example, in the case i draw,  BFS will return A-->B-->C but it's not the shortest path. I am not sure if my idea is right. Would you please look at it?

Thanks!

[James Feher]

When using a priority queue, that path wouldn't be returned because
there are still shorter paths to consider. A-D-E would be the shortest
path so that would be polled, then A-D-E-F, then A-D-E-F-C. At this
point, the first element in the queue has visited C, it is the
shortest path and is returned. If at any point A-B-C was shorter than
all other possible paths, then it would be returned

[Chong Wang]

all right. how about i change A--> D into 2 and A-->B into 1?

[Christina Brandt]

The weighted BFS algorithm that you learned in class DOES return the least costly path; rather than putting just the weight of the edge (u,v) into the PQ, it puts the weight of the path from starting node to v in the PQ. Take a look at the pseudocode from the slides:

Input: start node s, destination node t
•Put start (s,0,null) into min-priority queue.
•While queue not empty
    –Poll minimum element (n,c,prev) off queue and mark n as visited.
    –IF n equals t THEN return path
    –FOR all (unmarked) successors n’ of n
•Put (n’,c+weight(n,n’),n) into priority queue

cheers
Christie

[Chong Wang]

it makes more sence. Thank you!