Weighted Paths

Here are some questions to ask about a particular problem:
  1. Single source or all source?
  2. If single source, single pair or not?
  3. Directed or undirected?
  4. Are there negative weights?
  5. Are there cycles?
  6. If there cycles and negative weights, are there negative cycles?
  7. Does the graph have any special properties that may be useful? Examples include
    1. sparseness
    2. monotonicity property of some sort,
    3. layered property,
    4. other properties (what?).
  8. Is your information about the graph restricted in some way, such as:
    1. "pay to look" (this comes up with graphs whose weights must be computed on the fly),
    2. an online condition (meaning that you can't look at everything at once).
  9. Of course, finding maximum weight paths is equivalent to finding minimum weight paths. But what about finding optimal alternating paths in a game graph?

Some algorithms.
  1. Simple-minded dynamic programming; directed acyclic graph only.
  2. Tropical matrix multiplication
  3. Floyd-Warshall
  4. Dijkstra
  5. Bellman-Ford
  6. Johnson
  7. A* ("A star")

Back to Course Page