Answer to Question #221893 in Discrete Mathematics for ssssssss

Question

State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge weights.

2. Find the shortest path spanning tree for the weighted directed graph with vertices A, B, C, D, and

E given using Dijkstra’s algorithm.

Answer 1

Dijkstra's algorithm solves the shortest path problem for a directed weighted graph with non-negative weights. As the weights are non-negative, consequently, it is assumd that w(e) ≥ 0 for all e ∈ E .

The algorithm maintains a priority queue minQ that is used to store the unprocessed vertices with their shortest-path estimates est(v) as key values. It then repeatedly extracts the vertex u which has the minimum est(u) from minQ and relaxes all edges incident from u to any vertex in minQ. After one vertex is extracted from minQ and all relaxations through it are completed, the algorithm treats this vertex as processed and doesn't consider it again. The algorithm stops either when the priority queue (minQ) is empty or when every vertex is examined exactly once.

(2).

shortest path to D: E - D, cost=2

shortest path to C: E - C, cost=3

shortest path to B: E - C - B, cost=4

shortest path to A: E - C - A, cost=6

The minimum spanning tree: