Loading...
Please wait, while we are loading the content...
Similar Documents
All-pairs shortest-paths computation in the presence of negative cycles (2001).
| Content Provider | CiteSeerX |
|---|---|
| Author | Mehlhorn, Kurt Priebe, Volker Schäfer, Guido Sivadasan, Naveen |
| Abstract | We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n² log n), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance (v; w) between each pair µ(v, w) of vertices even in the presence of negative cycles, where µ(v, w) is defined as the inmum of the costs of all directed paths from v to w. |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Content Type | Text |