Types

Path Algorithms

When dealing with path algorithms, we are almost always concerned with the shortest path. The algorithm for calculating the shortest path often goes by the name Dijkstra's Algorithm. The general idea is that we want to find the shortest path/distance from vertex S to vertex T. Below is the process/algorithm to find that.

STEP 1

Assign to vertex S potential 0;

label each vertex V reached directly from S with the distance from S to V;

chose the smallest of these labels, and make it the potential of the corresponding vertex or

vertices.

GENERAL STEP

Consider the vertex or vertices just assigned a potential;

for each such vertex V, look at each vertex W reached directly from V and assign W the label

(potential of V)+(distance from V to W),

unless W already has a smaller label;

when all such vertices W have been labeled, choose the smallest label in the network which is

not already a potential and make it as potential at each vertex where it occurs;

repeat the GENERAL STEP with the new potential(s).

STOP

when vertex T has been assigned a potential; this is the shortest distance from S to T.

SHORTEST PATH(S)

Work backwards from T and include VW whenever

(potential of W)-(potential of V)=(distance from V to W).

This is the algorithm that we should follow to calculate the shortest path. To explore more about this algorithm and how it works, visit:
http://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_en.html