Graphs and Network Algorithms · Shortest Paths

Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths from one source when edge weights are nonnegative.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

Students learn the algorithm as a careful extension of BFS with weighted distances.

Guided Lesson Notes

Understanding Dijkstra's Algorithm

Dijkstra's Algorithm focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Dijkstra's algorithm finds shortest paths from one source when edge weights are nonnegative.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Dijkstra's Algorithm when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Dijkstra's Algorithm

Key Ideas

Distance estimates
Priority queue frontier
Nonnegative-weight requirement

Practice Prompts

Trace Dijkstra on a weighted graph.
Explain why a priority queue improves the next-node choice.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Dijkstra's Algorithm

Trace a small input, focusing on distance estimates.

1Write a small input where Dijkstra's Algorithm is clearly useful.
2Label the part of the input related to Distance estimates.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Adjacency-list traversal	O(V + E)	DFS and BFS visit vertices and inspect edges.
Adjacency matrix storage	O(V^2)	A matrix reserves space for every possible pair.
Weighted optimization	Varies	MST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Dijkstra's Algorithm interview problem: Network Delay Time

Interview medium

Problem

Given a directed weighted network and a starting node, find how long it takes for the signal to reach every node.

Input

The first line contains n, m, and source. The next m lines contain directed edges u v w.

Output

Print the maximum shortest-path distance from source, or -1 if some node cannot be reached.

Sample Input

Sample Output

Why the sample works

Node 4 is reached through 2->3->4 with total cost 2, which is the slowest reachable time.

Approach

1Build an adjacency list of directed weighted edges.
2Run Dijkstra from the source.
3Use a min-heap so the next finalized node has the smallest known distance.
4If any node stays unreachable, print -1; otherwise print the maximum distance.

O((n + m) log n) time and O(n + m) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int source = sc.nextInt();

    List<int[]>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

    for (int i = 0; i < m; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      int w = sc.nextInt();
      graph[u].add(new int[] {v, w});
    }

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.add(new int[] {source, 0});

    while (!pq.isEmpty()) {
      int[] cur = pq.remove();
      int node = cur[0];
      int cost = cur[1];
      if (cost != dist[node]) continue;

      for (int[] edge : graph[node]) {
        int next = edge[0];
        int nextCost = cost + edge[1];
        if (nextCost < dist[next]) {
          dist[next] = nextCost;
          pq.add(new int[] {next, nextCost});
        }
      }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
      if (dist[i] == Integer.MAX_VALUE) {
        System.out.println(-1);
        return;
      }
      answer = Math.max(answer, dist[i]);
    }

    System.out.println(answer);
  }
}

Python Solution

import heapq

n, m, source = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dist = [float('inf')] * (n + 1)
dist[source] = 0
heap = [(0, source)]

while heap:
    cost, node = heapq.heappop(heap)
    if cost != dist[node]:
        continue
    for nxt, weight in graph[node]:
        next_cost = cost + weight
        if next_cost < dist[nxt]:
            dist[nxt] = next_cost
            heapq.heappush(heap, (next_cost, nxt))

answer = max(dist[1:])
print(-1 if answer == float('inf') else answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Dijkstra's Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler