|
Whenever the edges of a graph are assigned a capacity it is possible
to compute the maximum flow and the minimum cut of the graph.
Whenever the edges of a graph are assigned a weight it is possible
to find shortest paths in the graph.
If one wants to perform these computations on a graph
where none of its edges have been assigned a capacity or a weight,
then the edges are taken to have a capacity or weight of one, and the
computations are carried out accordingly.
The flow-based and shortest-paths algorithms and the resulting
functionalities are fully documented in Chapter MULTIGRAPHS,
Sections Maximum Flow and Minimum Cut and Distances, Shortest Paths and Minimum Weight Trees
respectively.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|