Dijkstra’s Algorithm

Dijkstra’s Algorithm is a #202204151143 to find the #shortest path for weighted graph.

First, select a vertex that has the smallest weight among other unknown vertices (the weight for edges to all other vertices other than root could be declared as infinite whereas the root vertex will have 0 weight) in the graph. Then, after all the weight of the edges to its adjacent vertices are updated if they are smaller than the current value, the shortest path between the vertex and its adjacent vertices is declared as known. The same steps will proceed to all other unknown vertices until all shortest path to the vertices are declared known.

Analysis

• It will result in \(\Theta(\vert E \vert + \vert V \vert^2)\) or simply \(\Theta(\vert V \vert^2)\)
• For sparse graph, we could use 202202062259 to increase the runtime to \(O(\vert E \vert \log \vert V \vert)\) by using its DeleteMin after the smallest vertex has been found and DecreaseKey to decrease the distance of W to the distance of V + \(c_{v,w}\) if the latter is smaller. This could be implemented in Paring Heap.
• By using Fibonacci Heap, it could result in \(O(\vert E \vert + \vert V \log \vert V \vert)\).

Attention

• It is not wise to use this algorithm to calculate the shortest path for a graph with negative edge costs#.

Implementation

void Dijkstar(Table T)
{
  Vertex V, W;

  for (;;) {
    V = smallest unknown distance vertex; //
    if (V == NotAVertex)                  // Could be replaced by DeleteMin
      break;                              //

    T[V].Known = True;
    for each W adjacent to V
      if (!T[W].Known)
        if (T[V].Dist + Cvw < T[W].Dist) {  // Cvw: the weight for edge (v,w)
          // Update W
          Decrease(T[W].Dist to T[V].Dist + Cvw); // Could be replaced by DecreaseKey
          T[W].Path = V;
        }
  }
}