Answer to Question #118956 in Discrete Mathematics for inv

Question

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

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.