top of page

The BFS algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G. Can the Dijkstra's algorithm be used in place of BFS? In a different scenario, the Djik...


The question at hand is: The BFS algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G. Can Dijkstra's algorithm be used in place of BFS? In a different scenario. Dijkstra's algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G'. Can BFS be used in place of the Dijkstra's algorithm? Explain your answers for both scenarios.


Before we answer this question, you should know what BFS Algorithm and Dijkstra's Algorithm is. If you do not know what these algorithms are, I suggest that you read my article on these algorithms.


We know that Dijkstra's Algorithm is applied on a weighted graph. If we try applying Breadth First Search on such a graph, the algorithm fails. Hence, we cannot use BFS in place of Dijkstra's Algorithm.





However, when it comes to unweighted graphs, the situation is different. We know that usually BFS is applied to unweighted graphs only. When we replace this algorithm with Dijkstra's Algorithm, no major effect takes place because unweighted graph is just a weighted graph with all weights as ZERO or NULL.


Hence, Dijksta's Algorithm CAN be used in place of BFS Algorithm. However, BFS Algorithm cannot be used in place of Dijksta's Algorithm.

27 views0 comments

Commentaires


bottom of page