|
Find the set of edges connecting all nodes such that the
sum of the edge lengths from the root to each node is minimized
GREEDY ALGORITHM FOR SPT
Initial
Select the root node to form the set S1. Assign the path length
0 to this node. Put all other nodes in the set S2.
Selection
Compute the lengths of the paths to all nodes directly reachable
from S1 through a node in S1. Select the node in S2 with the
smallest path length.
Let the edge connecting this node with S1 be (i, j). Add this
edge to the shortest path tree. Add node j to the set S1 and
delete it from the set S2.
Finish
If the set S1 includes all the nodes, stop with the shortest
path tree. Otherwise repeat the Selection step.
|
