Graph Magics

Partners

DocsPal
Free online file Converter and Viewer

Shortest Path

Task:

Find the shortest path between two nodes (points).

Solution:

The most famous solution for this problem was first proposed by Dijkstra. Generally, his solution is the most efficient and used in most cases.

Algorithm:

Set the distance to source node to 0, and the distances to all other nodes to infinity.
Among all unprocessed nodes find the one that has the minimum distance to it yet found. Let this node be i. If i is the destination (end) node then exit because the shortest path from source to destination has been found. Otherwise mark it as processed and go to point 3.
Note: If distances to all unprocessed nodes are equal to Infinity then no path from source to destination node exists.
Look at each unprocessed neighbor j of node i. If the shortest distance to j is greater than the shortest distance to i + the cost of the edge between these 2 nodes, then update the shortest distance/path to j with this one and mark that it has been reached from i.
Go back to point 2.

Pseudocode:

# N - number of nodes
# weight(i,j) - weight of the edge from node i to j ; equal to infinity if such an edge doesn't exist
# dist(i) - the shortest path from source node to i
# parent(i) - node that precedes i in a shortest path, used to reconstruct the shortest path

# initialize all values
For i = 1 to N
    dist(i) = infinity
    processed(i) = false
    parent(i) = null
End For
dist(source) = 0

While (not all nodes have been processed)
    If (distances to all unprocessed nodes are equal to infinity) Then
        no path from source to destination node exists
        Exit
    End If

    Let i be an unprocessed node for which dist(i) is the smallest among all unprocessed nodes.
    If i = destination Then Exit While    # shortest path from source to destination has been found
    Set processed(i) = true

    For Each unprocessed node j    # i.e. for which processed(j) = false
        If dist(i) + weight(i,j) < dist(j) Then
            # a shorter path from source node to j has been found ; update it
            dist(j) = dist(i) + weight(i,j)
            parent(j) = i
        End If
    End For
End While

# the length of the shortest path is thus dist(destination)

# path reconstruction is given below
Set i = destination
While i != source
    Append i to the beginning of the currently constructed path
    i = parent(i)
End While
Append source to the beginning of the path

Complexity:

In average each of N nodes is processed, and for each all of its neighbors are updated in O(N). Thus the complexity is O(N²).

Restrictions:

This algorithm doesn't work for graphs that have negative edges. For these you should use Bellman-Ford algorithm, that runs in O(NM), where M is the number of edges.

Optimizations:

For sparse graphs a complexity of O(NlogN) may be obtained. For this purpose a heap is used to store the shortest distances to nodes, and neighbors of each node are stored in lists. In this way the unprocessed node with the minimum distance is found in logN and the update of each node is also done in logN.
Providing that the graph is sparse, each node has few neighbors and thus the average complexity is O(NlogN).
If edges have no costs then a Breadth First Search (BFS) algorithm can be applied to find the shortest path. It would run substantially faster, especially for graphs that have structures similar to mazes, tables, where each point has few neighbors.

Extensions:

If the above code is run until all nodes are processed (or until no unprocessed node is reachable) then we will get the shortest paths from source point to all other points (those that are reachable from it).

Sample Execution:

Given:

A sample graph made in Graph Magics. node 1 is start (source) node and 2 is end (destination) node. We need to find the shortest path between these two nodes.

Below execution steps of this algorithm are shown (all images are created in Graph Magics).

Legend:
- unprocessed nodes are colored in light gray
- current node (the one that is being processed) is colored in blue
- processed nodes are colored in red
- the number on a node represents the shortest path length to it yet found

Starting state:

Node	Processed	Distance from Source	Parent
1	false	0	null
2	false	Infinity	null
3	false	Infinity	null
4	false	Infinity	null
5	false	Infinity	null
6	false	Infinity	null
7	false	Infinity	null

Download this graph (viewable with Graph Magics)

Among all unprocessed nodes, 1 has the minimum distance from the source.

After updating the neighbors of node 1:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	Infinity	null
3	false	5	1
4	false	Infinity	null
5	false	Infinity	null
6	false	15	1
7	false	Infinity	null

Among all unprocessed nodes, 3 has the minimum distance from the source.

After updating the neighbors of node 3:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	Infinity	null
3	true	5	1
4	false	Infinity	null
5	false	30	3
6	false	15	1
7	false	Infinity	null

Among all unprocessed nodes, 6 has the minimum distance from the source.

After updating the neighbors of 6:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	45	6
3	true	5	1
4	false	20	6
5	false	30	3
6	true	15	1
7	false	25	6

Among all unprocessed nodes, 4 has the minimum distance from the source.

After updating the neighbors of 4:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	40	4
3	true	5	1
4	true	20	6
5	false	30	3
6	true	15	1
7	false	25	6

Among all unprocessed nodes, 7 has the minimum distance from the source.

After updating the neighbors of 7:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	40	4
3	true	5	1
4	true	20	6
5	false	30	3
6	true	15	1
7	true	25	6

Among all unprocessed nodes, 5 has the minimum distance from the source.

After updating the neighbors of 5:

Node	Processed	Distance from Source	Parent
1	true	0	null
2	false	40	4
3	true	5	1
4	true	20	6
5	true	30	3
6	true	15	1
7	true	25	6

2 is the node that has the shortest path to it yet found among all unprocessed nodes (in this example it is the only one left).
So we stop here the execution because we have found the shortest path from source to destination node (i.e. from 1 to 2).

Shortest path found:
1 >> 6 >> 4 >> 2

Cost of the path - 40

Applications:

This is probably the most used graph algorithm. It may be applied in situations where the shortest path between 2 points is needed. Examples of such applications would be:

Computer games - finding the best/shortest route from one point to another.
Maps - finding the shortest/cheapest path for a car from one city to another, by using given roads.
May be used to find the fastest way for a car to get from one point to another inside a certain city. E.g. satellite navigation system that shows to drivers which way they should better go.

A maze

The shortest path between the corners of the maze