Weighted Directed Graph

A DirectedGraph with a weight attached to each edge. There are many different ways to implement this DataStructure; which way is the best is application-dependent. [Examples?]

The weights are often numbers, but need not be; they can be whatever you want them to be, as long as you give them a suitable interpretation.

http://www.sics.se/SICS-reports/SICS-T--93-02--SE/report_11.html appears to describe some library utilities for dealing with WeightedDirectedGraphs. In that specific context, the following description is given:

: "A weighted directed graph (wgraph) is represented as a list of (vertex-edgelist) pairs, where the pairs are in standard order (as produced by keysort with unique keys), the edgelist is a list of (neighbor-weight) pair also in standard order (as produced by keysort with unique keys), every weight is a nonnegative integer, and every neighbor appears as a vertex even if it has no neighbors itself."

A common operation on weighted (directed) graphs is the shortest-path computation; the determination of the path(s) from two nodes A and B such that the sum of the weights of the vertices on the path is minimal. (You can replace summation with another operation).

In the case of summation; one can always find a shortest path unless there is a cycle with a negative net weight present; in which case there is no shortest path as one can round the cycle an infinite number of times, each time reducing the total weight of the path.