Edmonds' algorithm

When nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used to find a maximum or minimum path length. Instead an optimum branching algorithm should be applied using the algorithm proposed by Edmond (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.

References

J. Edmonds, “Optimum Branchings”, J. Res. Nut. Bur. Standards, vol. 71B, 1967, pp. 233-240.