Scribd
Upload
32 views2 pages

Dijkstra’s Algorithm – Shortest Path in Weighted Graphs

Dijkstra’s Algorithm is used to find the shortest path from a source node to all other nodes in a weighted graph with non-negative edges, commonly applied in GPS routing and network optimization. The algorithm involves assigning distances, updating tentative distances for unvisited neighbors, and iteratively selecting the node with the smallest distance. Its time complexity is O(V²) with an array and O((V+E) log V) with a heap, while the space complexity is O(V).

Uploaded by

rohitmishra007776
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
32 views2 pages

Dijkstra’s Algorithm – Shortest Path in Weighted Graphs

Dijkstra’s Algorithm is used to find the shortest path from a source node to all other nodes in a weighted graph with non-negative edges, commonly applied in GPS routing and network optimization. The algorithm involves assigning distances, updating tentative distances for unvisited neighbors, and iteratively selecting the node with the smallest distance. Its time complexity is O(V²) with an array and O((V+E) log V) with a heap, while the space complexity is O(V).

Uploaded by

rohitmishra007776
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

1.

Introduction

Dijkstra’s Algorithm finds the shortest path from a source node to all other nodes in a weighted
graph with non-negative edges. It’s widely used in GPS routing and network optimization.

2. How It Works

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

2. Set the source node as current.

3. For each unvisited neighbor, calculate tentative distances and update if smaller.

4. Mark the current node as visited.

5. Select the unvisited node with the smallest distance and repeat.

3. Pseudocode

sql

CopyEdit

procedure dijkstra(Graph, source):

dist[source] = 0

create priority queue Q

for each vertex v in Graph:

if v ≠ source:

dist[v] = ∞

enqueue(Q, v)

while Q not empty:

u = vertex with min dist in Q

remove u from Q

for each neighbor v of u:

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

if alt < dist[v]:

dist[v] = alt

4. Example
Graph: A→B(1), B→C(2), A→C(4)
Source: A
Output: A→B=1, A→C=3

5. Complexity Analysis

 Time Complexity: O(V²) with array, O((V+E) log V) with heap

 Space Complexity: O(V)

You might also like