+ - Finding My Summer Vacation's Shortest Path->
Submitted
by
CowboyRobot
CowboyRobot writes "Clay Breshears at Dr. Dobb's has a fun formula for optimizing the drive between multiple cities. "Think of a map as an instance of a graph, the cities are the nodes and the roads between cities are the edges. The length of the road is the weight of the corresponding edge. The All-Pairs Shortest Path problem takes a graph of n nodes represented by an n x n weight matrix, W. The result is an n x n matrix, D (for distance), where the D[i][j] entry holds the minimum weight of the path from node i to node j. Entries in the W matrix can be zero, positive (if a direct edge lies between the two nodes), or the infinity value where there is no direct edge between the nodes.""
Link to Original Source
Link to Original Source
Finding My Summer Vacation's Shortest Path More Login
Finding My Summer Vacation's Shortest Path