Methods

Network Flow Programming Minimal Spanning Tree/Shortest Path Tree Prim's Algorithm Dijkstra's Algorithm Download

Consider the undirected network as shown in the figure. The graph consists of nodes and edges, and each edge has an associated length. An edge is the line segment connecting two nodes and has the same length in either direction.

The Minimal Spanning Tree problem is to select a set of edges so that there is a path between each node. The sum of the edge lengths is to be minimized.

When the edge lengths are all nonnegative, as assumed here, the optimum selection of edges forms a spanning tree. Because of this characteristic of the solution, the problem is called the minimum spanning tree problem. The problem can be solved with a greedy algorithm called Prim's Algorithm. Click the link below to see the statement of the algorithm and a demonstration.

Prim's Algorithm

The algorithm is one of the simplest in optimization theory. The optimum is found after m -1 performances of the selection step, where m is the number of nodes.

We consider again the same undirected graph, but now we solve a different problem. The graph consists of nodes and edges, and each edge has an associated length. In this problem we identify a root node and desire to find a path to each node from the root node such that the length of the path to each node is minimized.

The Shortest Path Tree problem is to find the set of edges connecting all nodes such that the sum of the edge lengths from the root to each node is minimized

Again assume all edge lengths are nonnegative. The optimum selection of edges forms a spanning tree. The problem can be solved with a greedy algorithm called Dijkstra's Algorithm. Click the link below to see the statement of the algorithm and a demonstration.

Dijkstra's Algorithm

The algorithm is adapted easily to directed networks with nonnegative arc lengths. The optimum is found after m -1 performances of the selection step.