Check out my first novel, midnight's simulacra!

Suurballe's Algorithm

From dankwiki
Revision as of 17:07, 13 August 2012 by Dank (talk | contribs) (Created page with "An algorithm to find two paths in a nonnegatively-weighted directed graph, such that the two paths connect the same vertices, are otherwise disjoint, and minimize path lenghts...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An algorithm to find two paths in a nonnegatively-weighted directed graph, such that the two paths connect the same vertices, are otherwise disjoint, and minimize path lenghts. There exist obvious applications to routing survivability and network flow. The algorithm involves running Dijkstra twice.