Revision as of 22:06, 4 April 2008 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,738 edits why non-negative reweighted edges is a useful condition ← Previous edit		Revision as of 22:07, 4 April 2008 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,738 edits better link to sparsity Next edit →
Line 1: {{Tree search algorithm}} '''Johnson's algorithm''' is a way to solve the [[all-pairs shortest path problem]] in a [[sparse ~~matrix~~graph\|sparse]], [[weighted graph\|weighted]], [[directed graph]] in which some of the edge weights may be [[negative number]]s, but no negative-weight [[cycle (graph theory)\|cycles]] exist. It consists of the following steps:

Johnson's algorithm: Difference between revisions