The Shortest Path Problem
An Introduction |
Prof. David Bernstein
|
Computer Science Department |
bernstdh@jmu.edu |
O
denotes the origin nodeD
denotes the destination nodei
denotes the current working nodej
denotes an arbitrary nodeL[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
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,- | *,- | *,- | *,- | *,- |
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 |
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 |
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 | *,- |
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 |
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 |
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 | *,- |
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 |
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 |
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 | *,- |
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 |
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 |
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 | *,- |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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} |
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} |
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} |
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} |
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} |
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} |
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} |
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} |
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} |
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} |
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}/{}/{} |
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 |