[go: up one dir, main page]
Scribd
Upload
113 views2 pages

(S (1) For (I 2 I N I++) D (I) C (1, I) For (I 1 I n-1 I++)

The document describes Dijkstra's algorithm for finding the shortest path between nodes in a graph. It initializes a set S containing the starting node and distance values D for other nodes. It then iteratively finds the unvisited node with lowest distance, adds it to S, and updates other nodes' distances if the new path is shorter. This continues until all nodes are in S. The example shows the algorithm running on a graph until it finds the shortest distances between all nodes. Finally, it states that Dijkstra's algorithm has a time complexity of O(n^2) with an adjacency matrix, or O(elog n) with an adjacency list.

Uploaded by

bhariprasad_msc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
113 views2 pages

(S (1) For (I 2 I N I++) D (I) C (1, I) For (I 1 I n-1 I++)

The document describes Dijkstra's algorithm for finding the shortest path between nodes in a graph. It initializes a set S containing the starting node and distance values D for other nodes. It then iteratively finds the unvisited node with lowest distance, adds it to S, and updates other nodes' distances if the new path is shorter. This continues until all nodes are in S. The example shows the algorithm running on a graph until it finds the shortest distances between all nodes. Finally, it states that Dijkstra's algorithm has a time complexity of O(n^2) with an adjacency matrix, or O(elog n) with an adjacency list.

Uploaded by

bhariprasad_msc
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

{

S= { 1 };
for (i = 2; i < n; i++)
D[i] = C[1,i];
for (i=1; i < = n-1; i++)
{
choose a vertex w V-S such that D[w] is a minimum;
S = S {w };
for each vertex v V-S
D[v] = min (D[v], D[w] + C[w, v])
}
}



Initially:
S = {1} D[2] = 10 D[3] = D[4] = 30 D[5] = 100
Iteration 1
Select w = 2, so that S = {1, 2}
D[3] =
min( , D[2] + C[2, 3]) = 60
(7.2)
D[4] = min(30, D[2] + C[2, 4]) = 30 (7.3)
D[5] = min(100, D[2] + C[2, 5]) = 100
Iteration 2
Select w = 4, so that S = {1, 2, 4}
D[3] = min(60, D[4] + C[4, 3]) = 50 (7.4)
D[5] = min(100, D[4] + C[4, 5]) = 90
Iteration 3
Select w = 3, so that S = {1, 2, 4, 3}
D[5] = min(90, D[3] + C[3, 5]) = 60
Iteration 4
Select w = 5, so that S = {1, 2, 4, 3, 5}
D[2] = 10 (7.5)
D[3] = 50 (7.6)
D[4] = 30 (7.7)
D[5] = 60
Complexity of Dijkstra's Algorithm
With adjacency matrix representation, the running time is O(n2) By using an adjacency list
representation and a partially ordered tree data structure for organizing the set V - S, the
complexity can be shown to be
O(elog n)
where e is the number of edges and n is the number of vertices in the digraph.

You might also like