algorithmgraphshortest-pathbreadth-first-search# Using BFS for Weighted Graphs

I was revising single source shortest path algorithms and in the video, the teacher mentions that **BFS/DFS** can't be used directly for finding **shortest paths** in a **weighted graph** (I guess everyone knows this already) and said to work out the reason on your own.

I was wondering the exact reason/explanation as to why it can't be used for weighted graphs. Is it due to the weights of the edges or anything else ? Can someone explain me as I feel a little confused.

Solution

Consider a graph like this:

```
A---(3)-----B
| |
\-(1)-C--(1)/
```

The shortest path from A to B is via C (with a total weight of 2). A normal BFS will take the path directly from A to B, marking B as seen, and A to C, marking C as seen.

At the next stage, propagating from C, B is already marked as seen, so the path from C to B will not be considered as a potential shorter path, and the BFS will tell you that the shortest path from A to B has a weight of 3.

You can use Dijkstra's algorithm instead of BFS to find the shortest path on a weighted graph. Functionally, the algorithm is very similar to BFS, and can be written in a similar way to BFS. The only thing that changes is the order in which you consider the nodes.

For example, in the above graph, starting at A, a BFS will process A --> B, then A --> C, and stop there because all nodes have been seen.

On the other hand, Dijkstra's algorithm will operate as follows:

- Consider A --> C (since this is the lowest-edge weight from A)
- Consider C --> B (since this is the lowest-weight edge from any node we have reached so far, that we have not yet considered)
- Consider and ignore A --> B since B has already been seen.

Note that the difference lies simply in the *order* in which edges are inspected. A BFS will consider *all* edges from a single node before moving on to other nodes, while Dijkstra's algorithm will always consider *the lowest-weight unseen edge, from the set of edges connected to all nodes that have been seen so far*. It sounds confusing, but the pseudocode is very simple:

```
create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
vertex v = top of heap
pop top of heap
for each vertex u connected to v:
if dist[u] > dist[v] + weight of v-->u:
dist[u] = dist[v] + weight of edge v-->u
place u on the heap with weight dist[u]
```

This GIF from Wikipedia provides a good visualisation of what happens:

Notice that this looks very similar to BFS code, **the only real difference is the use of a heap, sorted by distance to the node, instead of a regular queue data structure**.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?