Unweighted Shortest Path

To calculate the #shortest path for unweighted graph, the following algorithm used the strategy breadth-first search where the siblings of the vertex get searched first which utilise the 202112101836.

Analysis

  • It will result in \(O(\vert E \vert + \vert V \vert)\)

Implementation

Note: An infinity distance between vertices indicates an unreachable position. 

void Unweighted(Table T) {
  Queue Q;
  Vertex V, W;

  Q = CreateQueue(NumVertex);
  MakeEmpty(Q);

  // Enqueue the start vertex S, which is known and T[S].Dist = 0
  Enqueue(S, Q);

  while (!IsEmpty(Q)) {
    V = Dequeue(Q);
    
    for each W adjacent to V
      if (T[W].Dist == Infinity) {
        T[W].Dist = T[V].Dist + 1;
        T[W].Path = V;
        Enqueue(W, Q);
      }
  }

  DisposeQueue(Q);
}
Links to this page
#graph #algorithm #queue