Dijkstra's algorithm

From Algorithmist

This is a stub or unfinished. Contribute by editing me.

Dijkstra's algorithm is a greedy algorithm for calculating the single source shortest path for a graph. It can also be used to calculate the shortest path spanning tree.

[edit] Algorithm

The algorithm is as follows, starting from source S:

1. Set distance to S to 0.
2. While there is a node to be relaxed
   1. Find the node V that is the closest to S that is not relaxed.
   2. Relax V - Adjust all adjacent vertices

Time complexity of the following algorithm is O(M log N), where M is amount of edges and N is amount of vertexes.

UM[x] is the total distance between the first vertex and x. S shows which vertexes are selected before. A is our matrix that shows the distances. For example, A[i][j] is the distance between i and j.

1. for(all the vertexes except the first vertex)
   1. UM[j] = A[first vertex][j]
2. UM[first vertex] = 0
3. CLEAR(S)
4. while(our target vertex doesn't exist in S)
   1. vertex = vertex with minimum distance that doesn't exist in S
   2. add vertex to S
   3. for(all the vertexes that don't exist in S)
      1. if(UM[vertex] + A[vertex][current vertex] < UM[current vertex])
         1. UM[current vertex] = UM[vertex] + A[vertex][current vertex];