The method to compute shortest a path between two given nodes s and t heavily depends on the configuration of arc length labels and orientations. The following list shows the available codes in decreasing order of computational efficiency, and it is recommended to apply the first method which is feasible for the given instance:
The general NP-hard setting with negative length cycles is not handled by the library.
Most library methods determine a shortest path tree routed at a given source node s rather than a single shortest path between a given node pair s and t, and this tree is exported by the predecessor labels. Specifying a target node t is relevant for the BFS and the Dijkstra method since the seach can be finished prematurely, when t is reached the first time. Only the T-join method constructs an exports a single st-path.
The following figure shows an undirected graph and a shortest path between the red filled nodes. Since negative length edges exist, only the T-join method is formally applicable (undirected edges are interpreted as antiparallel arc pairs in the other codes). If one inspects the graph thoroughly, one finds a negative-length cycle. In general, the T-join method will be aborted when extracting the st-path from the T-join subgraph in such a situation. But if the minimum T-join is nothing else than an st-path, it is a shortest st-path:
The following is a so-called Sierpinksi triangle. This is a recursively defined, infinite graph, and Eulerian at any recurrency level. An Eulerian cycle is displayed both by the edge labels and the edge colours:
The well-known Chinese postman problem asks for an increase of the upper capacity bounds (interpreted as arc multiplicities) such that the graph becomes Eulerian and the length of an Eulerian cycle is minimal. In the undirected setting (and only then), it is equivalent to determine a maximum length Eulerian subgraph. The library handles the directed and the undirected case, but not the generalized NP-hard problem for mixed graphs.
For the above graph, with the shown length labels and unit capacities, the following picture shows a maximum Eulerian subgraph in bold face, and a minimum length Eulerian augmentation:
Return to main page