šŸ’» Shortest Paths with Dijkstra's Algorithm

Explore greedy shortest path computation ā€” input a graph and source, watch Dijkstra find distances to all nodes step-by-step!

šŸŒ The Network Router's Quest

šŸŽÆ The Challenge:

You are tasked with finding the shortest communication paths from a source router to all other routers in a network using Dijkstra's algorithm. The network is a weighted graph (adjacency matrix).

šŸ“‹ Problem:

Compute minimum distances from source to all vertices and print in specified format.

Problem Specifications

  • Input: V (1 ā‰¤ V ā‰¤ 6). Next V lines: V x V adj matrix (0=no edge). Last: src (0 ā‰¤ src < V).
  • Output: Header "Vertex Distance from Source", then per vertex: "i\t\t\t distance" aligned.

Example: Input 1

3
0 2 5
2 0 1
5 1 0
0
012
Vertex 	Distance from Source
0			 0
1			 2
2			 3

šŸ”„ Dijkstra's Algorithm Strategy

Key Idea

  1. Initialize distances: inf except src=0.
  2. Use priority queue (min-heap) or simple scan for extract-min.
  3. While unvisited nodes: extract u with min dist.
  4. For each neighbor v of u: if dist[v] > dist[u] + w(u,v), update dist[v] and PQ.

Note: For Vā‰¤6, O(V^2) simple implementation suffices. Greedy: always extend shortest known path.

Simple Dijkstra

Time: O(V^2)
Space: O(V)

Bellman-Ford

O(V*E) ā€” works for negative but slower

šŸ” Step-by-Step Dijkstra Demo

Ready. Use controls below to start demo.

Adjacency Matrix

Current Distances

Priority Queue (min dist, node)

Distances will appear here

Progress Tracker

1. Init dist[src]=0, others inf; PQ with src
2. Extract min u from PQ
3. Mark u visited
4. Relax neighbors: if better, update dist & PQ
5. Repeat until PQ empty
6. Output formatted distances

šŸŽ® Build Your Dijkstra Shortest Paths

Enter V, matrix, src and press Compute

Examples

V=3, src=0
ā†’ 0 2 3
V=9, src=0 (large)
ā†’ 0 4 12 19 21 11 9 8 14

šŸ“Š Analysis & Optimization

Time

O(V^2)

Simple extract-min loop.

Space

O(V)

Dist array + visited.

Optimization Ideas

  • For larger V, use binary heap: O((V+E) log V).
  • Since Vā‰¤6, simple array scan for min is fine (O(V^2)).
  • In C++, use vector> for matrix; priority_queue for heap.