Scribd
Upload
8 views5 pages

Dijkstra Algorithm

Dijkstra's algorithm is a method for finding the shortest path in graphs with non-negative edge weights, developed by Edsger W. Dijkstra in 1956. It operates by maintaining sets of visited and unvisited vertices, selecting the unvisited vertex with the smallest tentative distance iteratively. The algorithm is applicable to both directed and undirected graphs, provided they are connected and have non-negative edge weights.

Uploaded by

abdelwahabbouchibane
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
8 views5 pages

Dijkstra Algorithm

Dijkstra's algorithm is a method for finding the shortest path in graphs with non-negative edge weights, developed by Edsger W. Dijkstra in 1956. It operates by maintaining sets of visited and unvisited vertices, selecting the unvisited vertex with the smallest tentative distance iteratively. The algorithm is applicable to both directed and undirected graphs, provided they are connected and have non-negative edge weights.

Uploaded by

abdelwahabbouchibane
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/ 5

Algorithm and Data Structure

Theme: Dijkstra Algorithm

Presented by:
Bouchibane Med Abdelwahab
Computer Science Student

Academic Year 2024–2025


Contents
1 What Is Dijkstra Algorithm ? 3

2 Can Dijkstra’s Algorithm work on both Directed and Undirected graphs? 3

3 Algorithm for Dijkstra’s Algorithm 4

4 How does Dijkstra’s Algorithm works? 4

1
List of Figures
1 Dijkstra Edsger (1930-2002) . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2
Algorithm and Data Structure Dijkstra Algorithm

1 What Is Dijkstra Algorithm ?


Dijkstra’s algorithm is a popular algorithm for solving single-source shortest path problems
having non-negative edge weight in the graphs i.e., it is to find the shortest distance between
two vertices on a graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in
1956. The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts

Figure 1: Dijkstra Edsger (1930-2002)

at the source vertex and iteratively selects the unvisited vertex with the smallest tentative
distance from the source. It then visits the neighbors of this vertex and updates their
tentative distances if a shorter path is found. This process continues until the destination
vertex is reached, or all reachable vertices have been visited.

2 Can Dijkstra’s Algorithm work on both Directed and


Undirected graphs?
Yes, Dijkstra’s algorithm can work on both directed graphs and undirected graphs as this
algorithm is designed to work on any type of graph as long as it meets the requirements of
having non-negative edge weights and being connected.

• In a directed graph, each edge has a direction, indicating the direction of travel
between the vertices connected by the edge. In this case, the algorithm follows the
direction of the edges when searching for the shortest path.

• In an undirected graph, the edges have no direction, and the algorithm can traverse
both forward and backward along the edges when searching for the shortest path.

3
Algorithm and Data Structure Dijkstra Algorithm

3 Algorithm for Dijkstra’s Algorithm


1. Mark the source node with a current distance of 0 and the rest with infinity.

2. Set the non-visited node with the smallest current distance as the current node.

3. For each neighbor, N of the current node adds the current distance of the adjacent
node with the weight of the edge connecting 0-¿1. If it is smaller than the current
distance of Node, set it as the new current distance of N.

4. Mark the current node 1 as visited.

5. Go to step 2 if there are any nodes are unvisited.

4 How does Dijkstra’s Algorithm works?

You might also like