Skip to main content

18. Shortest Paths & Dijkstras

Floyd-Warshall (FW)​

  • Suppose that wanted to find the shortest path between all pairs of start and end nodes
    • We would run Dijkstra from every node
    • Would then be a factor of O(∣V∣)O(|V|) worse than Dijkstra
  • But may be better to run a specific algorithm

All-Paris SPs​

  • The basic method has similarities to the methods for "change giving"
  • "Build the optimal answers using a subset of the nodes. Then add the effects of other nodes one at a time"

Data Structure​

d(i,j,k)

  • Shortest distance between nodes i and j
  • But using only the nodes {1,...,k} as potential allowed intermediary points

Initialisation of data structure​

d(i,j,0) = best distance between nodes i and j, but not using any intermediate nodes, so only using a singe edge, Hence d(i,j,0) = w(i,j) if there is an edge i to j = Inf otherwise