Lecture Notes for CS 512, Algorithm Design

Shortest Path Algorithms - 31 January 2000

1. shortest paths - given a weighted, directed graph find

   1. the shortest paths from a single source to all destinations

   2. the shortest paths to a single destination from all sources

   3. the shortest path from a single source to a single destination

   4. the shortest paths from any source to any destination

2. a weighted path, a shortest path, unreachable vertices, negative cycles

3. predecessor subgraph, shortest path tree

4. infinite arithmetic

5. facts about shortest paths

   1. a subpath of a shortest path is a shortest path

   2. the shortest path to a vertex is the shortest path to a neighbor plus the weight of the adjacent edge

   3. the shortest path to a neighbor plust the weight of the adjacent edge is an upper bound on the shortest path to a vertex

6. let's consider cuts again

   1. a non-trivial cut must contain an edge

   2. given edges across a cut, which edge to take

      1. the cut must contain all edges to a vertex

   3. but,

      1. how many cuts to take

      2. what's the shortest path to the neighbor

      3. which neighbor

      4. how long should the cuts be made

7. cut every vertex

8. obtain a high estimate for distance and improve it

9. use the lowest upper bound

   1. relaxation

10. what's the longest possible path

11. the result is the bellman-ford algorithm

12. indiscriminate cuts at every vertex is expensive - is there a better way

    1. if all v's neighbor's shortest paths are known

    2. define the cut to cross the frontier of the shortest-path tree

    3. unfortunately, this won't work because a frontier cut doesn't contain all edges to a node

    4. nowever, if all edges are non-negative, it doesn't matter

    5. dijkstra's algorithm

This page last modified on 31 January 2000.