Shortest Path
Dijkstra
O(n2)
algorithm
Path
1 -
2 1 2-->1
3 2 3-->2-->1
4 1 4-->1
5 1 5-->1
Floyd's Algorithm
O(n3)
# edges e < n^2
then use Dijkstra O(n * e * log n) for adjacency matrix
k = 1
A[2,1] + A[1,3] < A[2,3]
3 5 < infinity
Warshall's transitive closure: Take a set that is guaranteed to be transitive
Return to CIS 350 Index Page