Graph Magics



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:
  1. Set the distance to source node to 0, and the distances to all other nodes to infinity.

  2. 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.

  3. 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(N2).

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:

  1. 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).
  2. 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

 
Copyright 2004-2017 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.