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

Dijkstra

Dijkstra’s Algorithm is a method for finding the shortest path from a source vertex to all other vertices in a weighted, non-negative graph, developed by Edsger W. Dijkstra in the late 1950s. It is widely utilized in applications such as network routing and GPS systems. The algorithm operates by maintaining a set of nodes with known minimum distances and iteratively updating the distances of unvisited nodes until all nodes are processed.

Uploaded by

Subhadip Das
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
25 views2 pages

Dijkstra

Dijkstra’s Algorithm is a method for finding the shortest path from a source vertex to all other vertices in a weighted, non-negative graph, developed by Edsger W. Dijkstra in the late 1950s. It is widely utilized in applications such as network routing and GPS systems. The algorithm operates by maintaining a set of nodes with known minimum distances and iteratively updating the distances of unvisited nodes until all nodes are processed.

Uploaded by

Subhadip Das
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/ 2

Dijkstra’s Algorithm – Report

1. Introduction

Dijkstra’s Algorithm is a shortest path algorithm used in graph theory to find the shortest path
from a single source vertex to all other vertices in a weighted, non-negative graph. It was
conceived by Edsger W. Dijkstra in 1956 and published in 1959.

2. Purpose

The algorithm finds the shortest path from a source node to every other node in a graph. It is
widely used in network routing, maps/GPS systems, and pathfinding in AI.

3. How It Works

Dijkstra’s Algorithm maintains a set of nodes whose minimum distance from the source is already
known and calculates the tentative distance of the remaining nodes.

Steps:

1. Set the distance to the source node as 0 and all others as infinity.

2. Mark all nodes as unvisited.

3. Select the unvisited node with the smallest tentative distance.

4. For the current node, consider all its unvisited neighbors and calculate their tentative
distances.

5. Update the neighbor’s distance if the new path is shorter.

6. Mark the current node as visited.

7. Repeat until all nodes have been visited.

4. Algorithm (Pseudocode)

plaintext

CopyEdit

function Dijkstra(Graph, source):

dist[source] ← 0

for each vertex v in Graph:

if v ≠ source:

dist[v] ← ∞

prev[v] ← undefined

Q ← all nodes in Graph


while Q is not empty:

u ← vertex in Q with smallest dist[u]

remove u from Q

for each neighbor v of u:

alt ← dist[u] + weight(u, v)

if alt < dist[v]:

dist[v] ← alt

prev[v] ← u

return dist[], prev[]

5. Time and Space Complexity

Data Structure Used Time Complexity

Simple Array O(V²)

Min-Heap (Priority Queue) + Adjacency List O((V + E) log V)

• Space Complexity: O(V) for storing distances and previous nodes.

6. Example

Given a graph with nodes A, B, C, D, and E:

• Edges:
A → B (4), A → C (1),
C → B (2), B → D (1),
C → D (5), D → E (3)

Shortest path from A to E:


A→C→B→D→E

You might also like