There are many different operations that can be done on graphs. Methods such as Kruskal's algorithm and Prim's algorithm find the most efficient way to traverse an entire graph. However, if the distance (cost) between two given vertices needed to be calculated, an alternate method would be required. Dijkstra's algorithm determines the distances (costs) between a given vertex and all other vertices in a graph. This may be useful to determine alternatives in decision making. For example, a telephone company may forgo the decision to install a new telephone cable in a rural area when presented with the option of installing the same cable in a city, reaching twice the people at half the cost.

   Dijkstra's algorithm is almost identical to that of Prim's. The algorithm begins at a specific vertex and extends outward within the graph, until all vertices have been reached. The only distinction is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to the current vertex. More simply, Dijkstra's algorithm stores a summation of minimum cost edges whereas Prim's algorithm stores at most one minimum cost edge.

   Dijkstra's algorithm creates labels associated with vertices.  These labels represent the distance (cost) from the source vertex to that particular vertex. Within the graph, there exists two kinds of labels: temporary and permanent. The temporary labels are given to vertices that have not been reached. The value given to these temporary labels can vary. Permanent labels are given to vertices that have been reached and their distance (cost) to the source vertex is known. The value given to these labels is the distance (cost) of that vertex to the source vertex. For any given vertex, there must be a permanent label or a temporary label, but not both.   

   The algorithm begins by initializing any vertex in the graph (vertex A, for example) a permanent label with the value of 0, and all other vertices a temporary label with the value of 0.

   The algorithm then proceeds to select the least cost edge connecting a vertex with a permanent label (currently vertex A) to a vertex with a temporary label (vertex B, for example).   Vertex B's label is then updated from a temporary to a permanent label. Vertex B's value is then determined by the addition of the cost of the edge with vertex A's value.

   The next step is to find the next least cost edge extending to a vertex with a temporary label from either vertex A or vertex B (vertex C, for example), change vertex C's label to permanent, and determine its distance to vertex A.

   This process is repeated until the labels of all vertices in the graph are permanent.

Click here to view a formal definition of Dijkstra's Algorithm
Click here to see an interactive example.
Or move on to the next page to go directly to the next section.

Back to Prim's Algorithm

On to Flow Problems