Question
Answer problem using the shortest route problem steps as stated on top picture
SHORTEST ROUTE PROBLEM The shortest toate problem involves finding the shortest route (or least-cost or least time) from aty source node starting pointy any destination, through a network Each are in the hasanassociaied number e 20 which represents the distance, orcost,ortime, networkha from node i to node j 1. staring from the source mode. assign a permanent label to the source node, and node, while temporary labels leaving other modes unlabeled. The label is a pair of values in parentheses; the first value represents a distance from the source to that node along a specified route, and the second value represents the immediate preceding node on the specified route, 2, Select the temporary 1 whose first value is the smallest, and change it te a label. Any ties may be broken Once all modes the network have permanent labels, go to step 4 else go to step 3 3. Consider all nodes (excluding those that already have nett labels) that can be dethone this erty labeled mode in step 2 Let us reached directly from the permanentnode as N. Foreach nodethat can beteacheadisectly fromN,compute the mum of its distance nom N andthe value of 1he first component of the label ee N the nade in question is unlabeled, assign it a temporary label corsisting of this sum as the first component its label andNas the immediate preceding mode as second component of its label. If the node in question already has a 1 abel, give m lycalculated value of the first eempenem ofislabeliiless anew one only if the new than the current value of this first component. If this is the case, the new label will consist of this smaller first component, with Nas the preceding node. Renum to step 4. The permanent label indicates the shortest distance from the originto that node, and the preceding node on the shortest path. To find the shottest path to any given node, start at that node and move backward to its preceding node. Cortinur wwh this backward movement unt arriving at the origin. The sequence nodes traced forms of the shortest route between the origin and the node in question.
Explanation / Answer
The First permanent label is (0,_) (Node 1 - Roanoke)
All other are unlabelled labels.
There are 3 unlabelled cities reachable to Roanoke.
We label these 3 cities as (Label contains distance and the last city from which the distance is measured)
Staunton - (2,1)
Charlottesville - (4,1)
Richmond - (3,1)
The next permanent label is Staunton - (2,1)
There are 2 unlabelled cities reachable to Staunton.
We label these 2 cities as (Label contains distance and the last city from which the distance is measured)
Charlottesville - (2+1,2) = (3,2) This temporary label distance(3) is less then the previous temporary label distance. So we replace the new temporary label as (3,2)
Winchester - (2+2,2) = (4,2)
The next permanent label is Charlottesville - (3,2)
There are 2 unlabelled cities reachable to Charlottesville.
We label these 2 cities as (Label contains distance and the last city from which the distance is measured)
Washington DC - (3+2,3) = (5,3)
Richmond - (3+2,3) = (5,3)
The next permanent label is Washington DC - (5,3)
As the final destination is Washington DC, we can stop the process here as we have determined the shotest distance from Roanoke to Washington DC, which is 5.
The Shortest path (obtained by traversing the 2nd part of the label backward) is 1,2,3,5
that is, Roanoke -> Staunton -> Charlottesville -> Washington DC