April 2018
Beginner to intermediate
426 pages
10h 19m
English
The graph we used in this example is not a weighted graph. If we want to calculate the shortest path in weighted graphs (for example, what the shortest path is between city A and city B, an algorithm used in GPS and Google Maps), BFS is not the appropriate algorithm.
There is Dijkstra's algorithm, which solves the single-source shortest path problem, for example. The Bellman-Ford algorithm solves the single-source problem if edge weights are negative. The A* search algorithm provides the shortest path for a single pair of vertices using heuristics to try to speed up the search. The Floyd-Warshall algorithm provides the shortest path for all pairs of vertices.
We will explore Dijkstra's algorithm ...