[go: up one dir, main page]
Scribd
Upload
21 views8 pages

Dijkstra's Algorithm Overview

presentation slides of dijkshtra algorithm

Uploaded by

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

Dijkstra's Algorithm Overview

presentation slides of dijkshtra algorithm

Uploaded by

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

Dijkstra's

Shortest Path
Algorithm

Presented by:
Sushma Karki
Introduction

Dijkstra’s Algorithm is used to find the shortest path


from a source node to all other nodes in a graph with
non-negative weights.

Applications:
● Network routing
● GPS Navigation
● Telecommunications
Key concepts:
Graph: A collection of vertices (nodes) connected by edges
(links).

Weights: Non-negative values assigned to edges that represent


the cost or distance between two nodes.

Shortest Path: The path with the minimum total weight from the
source to the destination.
Algorithm:
Initialization: Start from the source node. Set its
distance to 0, and all other nodes to infinity.

Explore: Visit the unvisited node with the


smallest known distance and update its
neighboring nodes.

Repeat: Continue until all nodes are visited or


the shortest path to the destination is found.
Time Complexity
Using a simple array: O(V2)

Using a binary heap: O((V+E)logV)

Where:
● V = Number of vertices (nodes)
● E = Number of edges
● Advantages:
○ Efficient for graphs with non-negative weights.
○ Finds the shortest path from one source to all
other nodes.

● Limitations:
○ Doesn’t work with negative edge weights.
○ Can be slower for very large graphs.
Thank you!!
Have a nice day:)

You might also like