Dijkstra’s Algorithm
Dijkstra’s Algorithm finds the shortest path from a given node to other nodes in the graph.
It works by using a priority queue where it stores path distances.
Initially all distances are set to $infty$ apart from the distance to the start, which is 0.
Then, as long as there are elements in the queue, the algorithm takes off the minimum item from the queue, i.e., the node with the minimum distance, and relaxes the distance to its neighbors.
As an example, we will use a rectangular grid graph, which could represent a traffic grid.
Such a graph is represented by the traffic_grid_graph.txt file and looks as follows.
The numbers correspond to weights. The nodes are the black bullet points, and we assume they are numbered from 0, starting from the top left and proceeding left-to-right, top-to-bottom.
Dijkstra’s Algorithm
Dijkstra’s Algorithm finds the shortest path from a given node to other nodes in the graph.
It works by using a priority queue where it stores path distances.
Initially all distances are set to $infty$ apart from the distance to the start, which is 0.
Then, as long as there are elements in the queue, the algorithm takes off the minimum item from the queue, i.e., the node with the minimum distance, and relaxes the distance to its neighbors.
As an example, we will use a rectangular grid graph, which could represent a traffic grid.
Such a graph is represented by the traffic_grid_graph.txt file and looks as follows.
The numbers correspond to weights. The nodes are the black bullet points, and we assume they are numbered from 0, starting from the top left and proceeding left-to-right, top-to-bottom.