Below is a pseudo-code for solving shortest path problems. We used Dijkstra's Algorithm. Examing each line carefully. Understanding what is done in each step is very important!

// Let v1 be the origin vertex, 
//   and initialize W and ShortDist[u] as
   W := {v1}
   ShortDist[v1] :=0
   FOR each u in V - {v1}
      ShortDist[u] := T[v1,u]

// Now repeatedly enlarge W 
//   until W includes all verticies in V
   WHILE W <> V

      // Find the vertex w in V - W at the minimum distance
      //   from v1
      MinDist := INFINITE
      FOR each v in V - W
         IF ShortDist[v] < MinDist
            MinDist = ShortDist[v]
            w := v
         END {if}
      END {for}

      // Add w to W
      W := W U {w}

      // Update the shortest distance to vertices in V - W
      FOR each u in V - W
         ShortDist[u] := Min(ShorDist[u],ShortDist[w] + T[w,u])
   END {while}

Remember this is one type of algorithm to solve shortest path problems. There are also other algorithms to solve these problems.

Check other topics for the shortest path algorithm. They are all important.

Back to AlgoNet Home