Scribd
Upload
35 views15 pages

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between two nodes in a graph. It uses a greedy approach, starting at the start node and visiting the closest unvisited neighbor each time to build up the shortest path one step at a time. The algorithm works by maintaining a table of shortest distances and tracking visited versus unvisited nodes at each step.

Uploaded by

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

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between two nodes in a graph. It uses a greedy approach, starting at the start node and visiting the closest unvisited neighbor each time to build up the shortest path one step at a time. The algorithm works by maintaining a table of shortest distances and tracking visited versus unvisited nodes at each step.

Uploaded by

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

Dijkstra's algorithm

By Deekshant
What is Dijkstra's algorithm
Dijkstra's algorithm is an algorithm for finding the
shortest path between two nodes in a graph. It uses
greedy approach to find the shortest path.
How it works
Suppose we have a graph containing 5 nodes and some
connected edges with given weight and we want to
find the shortest path from start to end.

6
A B
5
1 2
2 C

5
E D
1
Start
End
6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B ∞
C ∞

5 D ∞
E D
1 E ∞

Visited = [] Unvisited = [A, B, C,


D, E]
6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B ∞
C ∞

5 D ∞
E D
1 E ∞

Visited = [A] Unvisited = [B, C, D,


E]
0 + 6
6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 6 A
C ∞

5 D ∞
E D
1 E 1 A
0 + 1

Visited = [A] Unvisited = [B, C, D,


E]
1 + 2
6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 3 E
C ∞

5 D 2 E
E D
1 E 1 A
1 + 1

Visited = [A, E] Unvisited = [B, C, D]


2 + 2
6
Shortest Previous
A B Vertex Distance Vertex
5 From A
2 + 5 A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D] Unvisited = [B,


C]
6
Shortest Previous
A B Vertex Distance Vertex
5 From A
3 + 5 A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D, B] Unvisited =


[C]
6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D, B, C] Unvisited = []


6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D, B, C] Unvisited = []


6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D, B, C] Unvisited = []


6
Shortest Previous
A B Vertex Distance Vertex
5 From A

A 0
2
1 2 C B 3 E
C 7 D

5 D 2 E
E D
1 E 1 A

Visited = [A, E, D, B, C] Unvisited = []


Pros
• Less complex
• Easy to implement
• Efficient for small graph

Cons
• Not efficient for large graphs
• Greedy approach
• Blinds search causes more time
Thank You.

You might also like