
Weighted Paths
Here are some questions to ask about a particular problem:
-
Single source or all source?
-
If single source, single pair or not?
-
Directed or undirected?
-
Are there negative weights?
-
Are there cycles?
-
If there cycles and negative weights, are there negative cycles?
-
Does the graph have any special properties that may be useful?
Examples include
-
sparseness
-
monotonicity property of some sort,
-
layered property,
-
other properties (what?).
-
Is your information about the graph restricted in some way, such as:
-
"pay to look" (this comes up with graphs whose weights must be
computed on the fly),
-
an online condition (meaning that you can't look at everything at once).
-
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.
-
Simple-minded dynamic programming; directed acyclic graph only.
-
Tropical matrix multiplication
-
Floyd-Warshall
-
Dijkstra
-
Bellman-Ford
-
Johnson
-
A* ("A star")

Back to
Course Page