Using Dijkstra\'s algorithm, find the shortest paths from node d to all other no

Question

Using Dijkstra's algorithm, find the shortest paths from node d to all other nodes in the transportation network shown below Consider the traffic network shown in Question . The travel demands between node d and all other nodes are given in Table below. Assume the travelers always travel along shortest paths only. Calculate the link flow in each link in the network Travel Demand (veh/h 100 50 Pair of Nodes 120 20 40 30 180 By using Floyd's algorithm find the shortest paths between all pairs of nodes in the transportation network shown below

Explanation / Answer

(1)

Consider the time for indirect links as infinity and the value is taken as 0 for node d and take the reference point as d and modify the value as and when required and select the minimal value

shortest path value for node a=6

shortest path =d-a

shortest path value for node b=6+5=11 (from node a)

shortest path value for node for node c=4

shortest path =d-c

shortest path value for node b=8 (from node c)

shortest path =d-c-b

shortest path value for node e=5 (from node d)

shortest path=d-e

shortest path value for node f=5+7=10 (from node e)

shortest path=d-e-f

shortest path value for node g=0+6=6 (from node d)

shortest path=d-g

shortest path value for node h=10+4=14 (from node f),12 (from node i)

shortest path=d-g-i-h

shortest path value for node i=9 (from node g), 19 (from node f)

shortest path=d-g-i

shortest path value for node j=12+3=15 (from node h), 9+3=12 (from node i)

shortest path=d-g-i-j

shortest path value for node k=11 (from node i), 12+2=14 from node j

shortest path=d-g-i-k

shortest path value for node L=14 (from node j), (11+3=14, from node k)

shortest path=d-g-i-j-L and d-g-i-k-L, both of them have equal values, so both are shortest paths.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.