Apply Dijkstra\'s single-source shortest path algorithm to the directed graph in

Question

Apply Dijkstra's single-source shortest path algorithm to the directed graph in Figure 2b with vertex d as the source, considering vertices in alphabetical order when there is a choice. Show your work by tracing the algorithm! (b) Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single-source shortest-path problem for a weighted connected graph G. i. Tme or false: T is a spanning tree of G? If true, briefly justify: if false, provide a small counterexample. ii. Tme or false: T is a minimum spanning tree of G? If true, briefly justify; if false, provide a small counterexample. (c) Give pseudocode for a linear-time algorithm for solving the single-source shortest-paths problem for directed acyclic graphs (DAGs) represented by their adjacency lists.

Explanation / Answer

Answer for Question:

As given in Question 2b is

Start with vertex a :

Step 1: Vertex d is have the b and c are the neighbouring
vertexes ..

distances from d to b is 3 and c is 6

b(2)
   |
   |
|
d(7)---------c(5)
  
Vertex b, c and d are having the loop..

Step 2: Consider vertex b has neighbouring vertexes are a and c

distances from b to a is 3 and b to c is 6

a(5)---- b(2)
   |
   |
|
d(7)---------c(5)
  
Here b and a , d are having loop.

Step 3: Consider Vertex e is having neighbouring vertexes
are d and e

a(5)---- b(2)
   |
   |
|
d(7)---------c(5)--------e(12)

Here d and c , e are having loop.

      
The shortest distances between from d to e is 12

Answer for Question 2 a:

T is a spanning tree of G is True

Answer for Question 2 b:

T is a minimum spanning tree of G is True.

Answer for Question 3:

function Dijkstra(Graph, source):

create vertex set Q

for each vertex v in Graph: // Initialization
dist[v] INFINITY // Unknown distance from source to v
prev[v] UNDEFINED // Previous node in optimal path from source
add v to Q // All nodes initially in Q (unvisited nodes)

dist[source] 0 // Distance from source to source
  
while Q is not empty:
u vertex in Q with min dist[u] // Source node will be selected first
remove u from Q
  
for each neighbor v of u: // where v is still in Q.
alt dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] alt
prev[v] u

return dist[], prev[]

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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