- Forward


The Shortest Path Problem
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

A Brief Review
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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.)
Back SMYC Forward

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
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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.)
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • 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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward

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

network_8node12arc
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)
Back SMYC Forward
  • 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
Back SMYC Forward

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

network_8node12arc
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
Back SMYC Forward
/imgs
(Courtesy of xkcd)
Things to Think About
Back SMYC Forward
  • 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 an intermediate "area"?
    • Suppose we want to find the shortest path from an origin to a destination via multiple intermediate points in any order?
  • Alternatives:
    • Suppose we want to find the 2nd, 3rd, 4th, etc. shortest path?
    • What does it mean for one path to be different from another?
There's Always More to Learn
Back -