Dijkstra’s Algorithm in Brief

Dijkstra’s AlgorithmDijkstra’s Algorithm solves the single source shortest path problem inO((E + V)logV)time, which can be improved toO(E + VlogV)when using a Fibonacci heap. This note requires that you understand basic graph theory terminology and concepts.Single Source Shortest Path (sssp)Thessspis to find the shortest distance from the source vertex to all other vertices in the graph. We can store this in a simple array.Psuedo-codeSet the distance to the source to 0 and the distance to the remaining vertices to infinity.Set thecurrentvertex to the source.Flag thecurrentvertex as visited.For all vertices adjacent to thecurrentvertex, set the distance from the source to theadjacentvertex equal to the minimum of its present distance and thesumof theweight of the edgefrom the current vertex to the adjacent vertex and the distance from the source to thecurrentvertex.From the set ofunvisited vertices, arbitrarily set one as the newcurrentvertex, provided that there exists an edge to it such that it is the minimum of all edges from a vertex in the set ofvisited verticesto a vertex in the set ofunvisited vertices. To reiterate: The new current vertex must be unvisited and have a minimum weight edges from a visited vertex to it. This can be done trivially by looping through all visited vertices and all adjacent unvisited vertices to those visited vertices, keeping the vertex with the minimum weight edge connecting it.Repeat steps 3-5 until all vertices are flagged as visited.Implementation#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1<<29;
int N, M, adj[1002][1002], dist[1002]; bool flag[1002];
void dijkstra(int s){
fill(dist, dist+1002, INF);
dist[s] = 0;
for(int i=1; i<=N; i++){
int d=INF, u=0;
for(int j=1; j<=N; j++)
if(!flag[j] && dist[j]< d){
d=dist[j]; u=j;
}
flag[u] = 1;
for(int j=1; j<=N; j++)
if(!flag[j])
dist[j]=min(dist[j], dist[u]+adj[u][j]);
}
}
int main(){
cin >> N >> M;
fill_n(&adj[0][0], 1002*1002, INF);
for(int i=0, u, v, w; i<M; i++){
cin >> u >> v >> w;
adj[u][v] = adj[v][u] = min(adj[u][v], w);
}
dijkstra(1);
for(int i=1; i<=N; i++)
if(flag[i]) cout << dist[i] << endl;
else cout << -1 << endl;
}DiagramProof of CorrectnessCLRSexplains it best, but theWikipedia pageis good as well.Priority QueueDijkstra’s algorithm can be easily sped up using apriority queue, pushing in all unvisited vertices during step 4 and popping the top in step 5 to yield the new current vertex.VisualizationsVisitVisuAlgo.

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *