Re: Graph optimization


Logan Shaw wrote:
[ ... ]
Although Dijkstra's
algorithm is going to be the best for finding the shortest path
between a single pair of points,

with non-negative edge weights. The OP didn't clarify that either.
Bellman-Ford otherwise (though negative weight cycles aren't allowed.)

[ snip more on Dijkstra ]

However, Dijkstra is of O(n^2), and running it for, say, all n nodes
gets the
complexity upto O(n^3), same as Floyd-Warshall, which does just just ;)
IMHO, a bit more elegantly. Caveat: negative edge weights are fine,
but not cycles.

.