The Shortest Path Problem

The Shortest Path Problem
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

A Brief Review

A Directed Graph/Network:
- A finite set of vertexes/nodes
- A finite set of edges/arcs/links, each of which is an ordered pair of nodes
A Walk:
- A sequence of arcs in which the head node of arc i is the tail node of arc i+1
A Path:
- A walk with distinct nodes and arcs

A Problem Set on a Graph/Network

Suppose:
- Each edge/arc/link has a length/weigh/cost
The Problem:
- Find the "shortest" path from a given origin node to a given destination node

Label Setting Algorithms

Setup:
- Associate a "label" with each node that represents the length of the shortest path to that node that has been found so far

An Overview:

Initialize all labels to infinity;

Initialize the label of the origin to 0;

Make the origin the working node;

while (The working node is not the destination)
{
    // Update the temporary labels
    for (All nodes that are reachable from the working node)
    {

      Calculate the distance to this node through the working node;

      if (This distance is less than the node's current label)
      {

        Set the node's label equal to this distance;

        Set the node's predecessor equal to the working node;
      }
    }

   // Greedily select the new working node
    for (All nodes with temporary labels) {

      Find the node with smallest temporary label;
    }

    Make the status of this node permanent;

    Set the working node equal to this node;

}

Label Setting Algorithms (cont.)

Notation for Nodes:
- O denotes the origin node
- D denotes the destination node
- i denotes the current working node
- j denotes an arbitrary node
Other Notation:
- L[n] denote the label for node n
- S[n] denotes the status of node n
- P[n] denotes the predecessor of node n
- d(i,j) denotes the distance from i to j

Label Setting Algorithms (cont.)

More Detailed Pseudo-Code

    When we start out, all of the nodes have temporary status;

    i = O;

    while (i != D) {

      for (All nodes j that are reachable from i) {

        if (L[i] + d(i,j) < L[j]) {

          L[j] = L[i] + d(i,j);
          P[j] = i;
        }
      }

      M = infinity;

      for (All nodes j with S[j]==temporary) {

        if (L[j]<M) {

          M = L[j];
          n = j;
        }
      }


      S[n] = permanent;

      i =  n;
    }

An Example

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1			1,4		12,4		8,4

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3					17,3

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5						15,7		16,7

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5					9,2	15,7		16,7

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5					9,2	15,7		16,7	5

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5					9,2	15,7		16,7	5
6								13,5

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5					9,2	15,7		16,7	5
6						15,7		13,5

An Example (cont.)

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Perm
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4		12,4	*,-	8,4	*,-	3
2	3,3	*,-			12,4	17,3	8,4	*,-	1
3		4,1			12,4	17,3	8,4	*,-	2
4					9,2	17,3	8,4	*,-	7
5					9,2	15,7		16,7	5
6						15,7		13,5	8

Label Correcting Algorithms

Setup:
- Associate a "label" with each node that represents the length of the shortest path to that node that has been found so far

An Overview:

Initialize all labels to infinity;

Initialize the label of the origin to 0;

Make the origin the working node;

while (There are candidates nodes)
{
    // Update the temporary labels
    for (All nodes that are reachable from the working node)
    {

      Calculate the distance to this node through the working node;

      if (This distance is less than the node's current label)
      {

        Set the node's label equal to this distance;

        Make this node a candidate;

        Set the node's predecessor equal to the working node;
      }
    }

   // Make any candidate node the new working node
   Choose a candidate node;

   Set the working node equal to this node;
}

Label Correcting Algorithms (cont.)

Obvious ways of selecting candidates:
- Most/least recently added node
- The tail node of long/short arcs
- A node with a "good" (though not best) label
Less obvious ways of selecting candidates:
- Use an approximation of the distance to the destination (e.g., Euclidean distance) [The A ^* Algorithm]
- Good candidates from paths connecting nearby O-D pairs

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}
6	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{3}/{1}/{1}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}
6	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{3}/{1}/{1}
7	3,3	4,1	1,4	0,-	12,4	15,7	8,4	16,7	{1}/{2}/{2}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}
6	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{3}/{1}/{1}
7	3,3	4,1	1,4	0,-	12,4	15,7	8,4	16,7	{1}/{2}/{2}
8	3,3	4,1	1,4	0,-	9,2	15,7	8,4	16,7	{2}/{5}/{5}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}
6	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{3}/{1}/{1}
7	3,3	4,1	1,4	0,-	12,4	15,7	8,4	16,7	{1}/{2}/{2}
8	3,3	4,1	1,4	0,-	9,2	15,7	8,4	16,7	{2}/{5}/{5}
9	3,3	4,1	1,4	0,-	9,2	15,7	8,4	13,5	{5}/{8}/{8}

An Example

Find the shortest path from 4 to 8 in the following network using last-in, first-out candidate selection.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Out/In/Candidates
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	{}/{4}/{4}
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	{4}/{3,5,7}/{3,5,7}
2	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{7}/{6,8}/{3,5,6,8}
3	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{8}/{}/{3,5,6}
4	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{6}/{}/{3,5}
5	*,-	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{5}/{}/{3}
6	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	{3}/{1}/{1}
7	3,3	4,1	1,4	0,-	12,4	15,7	8,4	16,7	{1}/{2}/{2}
8	3,3	4,1	1,4	0,-	9,2	15,7	8,4	16,7	{2}/{5}/{5}
9	3,3	4,1	1,4	0,-	9,2	15,7	8,4	13,5	{5}/{8}/{8}
10	3,3	4,1	1,4	0,-	9,2	15,7	8,4	13,5	{8}/{}/{}

The Bellman/Ford-Fulkerson/Moore Algorithm(s)

The Traditional Description:

Initialize all labels to infinity;

Initialize the label of the origin to 0;

for (As many iterations as there are vertices)
{
    // Update the temporary labels
    for (Each edge)
    {
      Calculate the distance to the head node through the tail node;

      if (This distance is less than the head node's current label)
      {
        Set the head node's label equal to this distance;

        Set the head node's predecessor equal to the tail node;
      }
    }
}

An Observation:
- In the inner iteration, the only labels that can change are head nodes of edges whose tail node changed in the previous iteration
An Interpretation:
- A label correcting algorithm in which, at each iteration, all candidates are processed

An Example

Find the shortest path from 4 to 8 in the following network.

Iter	1's Label	2's Label	3's Label	4's Label	5's Label	6's Label	7's Label	8's Label	Changed
0	*,-	*,-	*,-	0,-	*,-	*,-	*,-	*,-	4
1	*,-	*,-	1,4	0,-	12,4	*,-	8,4	*,-	3,5,7
2	3,3	*,-	1,4	0,-	12,4	15,7	8,4	16,7	1,6,8
3	3,3	4,1	1,4	0,-	12,4	15,7	8,4	16,7	2
4	3,3	4,1	1,4	0,-	9,2	15,7	8,4	16,7	5
5	3,3	4,1	1,4	0,-	9,2	15,7	8,4	13,5	8

Nerd Humor

http://imgs.xkcd.com/comics/pillow_talk.jpg

(Courtesy of xkcd)

Things to Think About

Ties:
- Suppose we want to find all of the shortest paths connecting an origin and destination?
All Pairs:
- Suppose we want to find the shortest path from every origin to every destination?
Intermediate Point:
- Suppose we want to find the shortest path from an origin to a destination via an intermediate point?
- Suppose we want to find the shortest path from an origin to a destination via multiple intermediate points in any order?