Shortest Path Algorithms in Graphs Tutorial

The shortest path problem asks us to find the minimum-cost path between two vertices in a graph. The cost can represent distance, time, money, network latency, or another measurable value associated with an edge.

The appropriate shortest path algorithm depends on the type of graph. For example, Breadth-First Search (BFS) is suitable for unweighted graphs, while Dijkstra's algorithm is commonly used for graphs with non-negative edge weights.

Other algorithms, such as Bellman-Ford and Floyd-Warshall, handle different requirements including negative edge weights and all-pairs shortest paths.

What Is a Shortest Path?

Consider a graph where the numbers on the edges represent distances:

A -- 4 -- B
|         |
2         3
|         |
C -- 1 -- D

If we want to travel from A to D, there may be multiple possible paths. The shortest path is the path whose total edge cost is the smallest.

For example:

A → B → D
Cost = 4 + 3 = 7

A → C → D
Cost = 2 + 1 = 3

Therefore, A → C → D has the smaller total cost for this example.

Types of Shortest Path Problems

Shortest path problems can be classified according to how many vertices are involved and what properties the graph has.

Problem	Description	Common Algorithm
Single-source shortest path	Shortest paths from one source to other vertices	BFS, Dijkstra, Bellman-Ford
Single-pair shortest path	Shortest path between two specific vertices	BFS or Dijkstra, depending on graph
All-pairs shortest path	Shortest paths between every pair of vertices	Floyd-Warshall

Choosing a Shortest Path Algorithm

Before implementing a shortest path algorithm, identify the properties of the graph.

Graph Condition	Suitable Approach
Unweighted graph	BFS
Weighted graph with non-negative weights	Dijkstra's algorithm
Weighted graph with negative edges	Bellman-Ford
Shortest paths between every pair	Floyd-Warshall

Shortest Path in an Unweighted Graph

When every edge has the same cost, the shortest path can be found using Breadth-First Search (BFS).

BFS explores vertices according to their distance from the starting vertex. The first time BFS reaches a vertex, it has found a shortest path to that vertex in terms of the number of edges.

A -- B -- C
|         |
D -------- E

Starting from A, BFS visits vertices according to their minimum number of edges from A.

BFS Shortest Path Implementation

function shortestPathBFS(graph, start, target) {
  const queue = [start];
  const distance = { [start]: 0 };
  const parent = { [start]: null };

  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];

    if (node === target) {
      break;
    }

    for (const neighbor of graph[node]) {
      if (distance[neighbor] === undefined) {
        distance[neighbor] = distance[node] + 1;
        parent[neighbor] = node;
        queue.push(neighbor);
      }
    }
  }

  if (distance[target] === undefined) {
    return null;
  }

  const path = [];
  let current = target;

  while (current !== null) {
    path.push(current);
    current = parent[current];
  }

  path.reverse();

  return {
    distance: distance[target],
    path
  };
}

const graph = {
  A: ["B", "D"],
  B: ["A", "C"],
  C: ["B", "E"],
  D: ["A", "E"],
  E: ["D", "C"]
};

console.log(shortestPathBFS(graph, "A", "E"));

The parent object stores how each vertex was reached. This makes it possible to reconstruct the actual shortest path instead of returning only its distance.

Why BFS Finds the Shortest Path

BFS processes vertices in layers:

Distance 0:
A

Distance 1:
B, D

Distance 2:
C, E

Because BFS completely processes one distance level before moving to the next, the first discovery of a vertex corresponds to the minimum number of edges required to reach it in an unweighted graph.

Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths from a source vertex in a weighted graph when all edge weights are non-negative.

Instead of processing vertices according to the number of edges, Dijkstra's algorithm repeatedly selects the unprocessed vertex with the smallest known distance.

It then attempts to improve the distances of neighboring vertices. This process is called relaxation.

Relaxation

Suppose the shortest known distance to vertex A is 5 and the edge from A to B has weight 3. If B currently has a distance of 10, traveling through A gives a better distance:

distance[A] + weight(A, B)
5 + 3
= 8

Current distance[B] = 10

New distance[B] = 8

This update is called relaxing the edge A → B.

Dijkstra's Algorithm Steps

Set the source distance to 0.
Set the initial distance of every other vertex to infinity.
Select the unprocessed vertex with the smallest known distance.
Relax its outgoing edges.
Mark the vertex as processed.
Repeat until the required vertices have been processed.

Dijkstra's Algorithm in JavaScript

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();

  for (const node of Object.keys(graph)) {
    distances[node] = Infinity;
  }

  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    let current = null;
    let smallestDistance = Infinity;

    for (const node of Object.keys(graph)) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        current = node;
      }
    }

    if (current === null) {
      break;
    }

    visited.add(current);

    for (const edge of graph[current]) {
      const { node: neighbor, weight } = edge;
      const newDistance = distances[current] + weight;

      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
      }
    }
  }

  return distances;
}

const graph = {
  A: [
    { node: "B", weight: 4 },
    { node: "C", weight: 2 }
  ],
  B: [
    { node: "A", weight: 4 },
    { node: "C", weight: 1 },
    { node: "D", weight: 5 }
  ],
  C: [
    { node: "A", weight: 2 },
    { node: "B", weight: 1 },
    { node: "D", weight: 8 }
  ],
  D: [
    { node: "B", weight: 5 },
    { node: "C", weight: 8 }
  ]
};

console.log(dijkstra(graph, "A"));

This implementation uses a simple scan to find the smallest unprocessed distance. More optimized implementations use a priority queue or min-heap.

Dijkstra with Path Reconstruction

If the application needs the actual path rather than only the shortest distance, store the predecessor of each vertex whenever its distance is improved.

function shortestPathDijkstra(graph, start, target) {
  const distances = {};
  const previous = {};
  const visited = new Set();

  for (const node of Object.keys(graph)) {
    distances[node] = Infinity;
    previous[node] = null;
  }

  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    let current = null;
    let smallestDistance = Infinity;

    for (const node of Object.keys(graph)) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        current = node;
      }
    }

    if (current === null) {
      break;
    }

    visited.add(current);

    for (const edge of graph[current]) {
      const { node: neighbor, weight } = edge;
      const newDistance = distances[current] + weight;

      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        previous[neighbor] = current;
      }
    }
  }

  if (distances[target] === Infinity) {
    return null;
  }

  const path = [];
  let current = target;

  while (current !== null) {
    path.push(current);
    current = previous[current];
  }

  path.reverse();

  return {
    distance: distances[target],
    path
  };
}

const graph = {
  A: [
    { node: "B", weight: 4 },
    { node: "C", weight: 2 }
  ],
  B: [
    { node: "D", weight: 5 }
  ],
  C: [
    { node: "B", weight: 1 },
    { node: "D", weight: 8 }
  ],
  D: []
};

console.log(shortestPathDijkstra(graph, "A", "D"));

Why Dijkstra Does Not Support Negative Edges

Dijkstra's algorithm relies on the fact that once the smallest-distance unprocessed vertex has been selected, its distance cannot later be improved through another path.

Negative edge weights can violate this assumption.

A → B = 4
A → C = 2
C → B = -5

A path through C can later produce a smaller distance for B. For graphs containing negative edge weights, Bellman-Ford is a more appropriate general-purpose single-source algorithm.

Bellman-Ford Algorithm

Bellman-Ford finds single-source shortest paths in graphs that may contain negative edge weights. It can also detect reachable negative-weight cycles.

The algorithm repeatedly relaxes every edge. For a graph with V vertices, it performs up to V - 1 complete relaxation passes because a simple shortest path cannot contain more than V - 1 edges.

function bellmanFord(vertices, edges, start) {
  const distance = {};

  for (const vertex of vertices) {
    distance[vertex] = Infinity;
  }

  distance[start] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let changed = false;

    for (const edge of edges) {
      const { from, to, weight } = edge;

      if (
        distance[from] !== Infinity &&
        distance[from] + weight < distance[to]
      ) {
        distance[to] = distance[from] + weight;
        changed = true;
      }
    }

    if (!changed) {
      break;
    }
  }

  for (const edge of edges) {
    const { from, to, weight } = edge;

    if (
      distance[from] !== Infinity &&
      distance[from] + weight < distance[to]
    ) {
      return {
        hasNegativeCycle: true,
        distance: null
      };
    }
  }

  return {
    hasNegativeCycle: false,
    distance
  };
}

const vertices = ["A", "B", "C"];

const edges = [
  { from: "A", to: "B", weight: 4 },
  { from: "A", to: "C", weight: 5 },
  { from: "B", to: "C", weight: -2 }
];

console.log(bellmanFord(vertices, edges, "A"));

Negative Cycles

A negative-weight cycle is a cycle whose total edge weight is negative.

A → B = 2
B → C = -5
C → A = 1

Total = 2 - 5 + 1
      = -2

If a negative cycle is reachable from the source, a finite shortest path may not exist because repeatedly traversing the cycle can continue reducing the total cost.

Floyd-Warshall Algorithm

Floyd-Warshall solves the all-pairs shortest path problem. Instead of selecting one source vertex, it computes the shortest distance between every pair of vertices.

The algorithm uses dynamic programming. For every possible intermediate vertex, it checks whether traveling through that vertex produces a shorter route.

function floydWarshall(matrix) {
  const distance = matrix.map(row => [...row]);
  const n = distance.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        distance[i][j] = Math.min(
          distance[i][j],
          distance[i][k] + distance[k][j]
        );
      }
    }
  }

  return distance;
}

const INF = Infinity;

const graph = [
  [0,   4,   2,   INF],
  [INF, 0,   1,   5],
  [INF, INF, 0,   8],
  [INF, INF, INF, 0]
];

console.log(floydWarshall(graph));

Floyd-Warshall can work with negative edge weights, provided there is no negative cycle affecting the shortest-path interpretation.

Shortest Path Algorithm Comparison

Algorithm	Graph	Negative Edges	Typical Time	Main Use
BFS	Unweighted	Not applicable	O(V + E)	Shortest path by number of edges
Dijkstra	Weighted	No	O((V + E) log V) with a suitable heap	Single-source shortest paths
Bellman-Ford	Weighted	Yes	O(VE)	Negative edges and cycle detection
Floyd-Warshall	Weighted	Yes	O(V³)	All-pairs shortest paths

Shortest Path and Path Reconstruction

Some applications need more than the minimum cost. They need the actual sequence of vertices or edges that forms the shortest route.

A common technique is to maintain a parent or previous value whenever a better distance is found.

previous[B] = A;
previous[C] = B;
previous[D] = C;

Starting from D and following the previous references backward reconstructs D → C → B → A. Reversing that sequence produces the path from A to D.

Shortest Path in a Grid

Grid problems can also be modeled as graphs. Each cell can represent a vertex, and movement between neighboring cells represents an edge.

S . .
# . #
. . T

If every movement has the same cost, BFS can find the shortest route from S to T. If movements have different non-negative costs, a weighted shortest-path algorithm such as Dijkstra's algorithm may be appropriate.

Real-World Applications

Maps: finding routes between locations.
Networking: determining low-cost or low-latency routes.
Games: finding movement paths through a game environment.
Logistics: selecting routes based on distance or transportation cost.
Dependency systems: analyzing relationships between components.
Robotics: finding paths through an environment.
Communication systems: optimizing routes between nodes.

Common Beginner Mistakes

Using BFS for weighted graphs where edge weights are different.
Using Dijkstra's algorithm when negative edge weights are present.
Forgetting to initialize unreachable distances to infinity.
Updating a distance without recording the predecessor when the actual path is required.
Confusing shortest distance with the path itself.
Assuming the shortest path always uses the fewest edges in a weighted graph.
Ignoring negative cycles when using algorithms that support negative edges.
Choosing an all-pairs algorithm when only one source-to-target path is required.

Interview Decision Pattern

When you encounter a shortest-path problem, first identify the graph properties:

Are the edges weighted?
If weighted, can any edge have a negative weight?
Do I need paths from one source or between every pair?
Do I need only the distance or the actual path?
Is the graph represented using an adjacency list or matrix?

These questions usually narrow down the appropriate algorithm quickly.

Key Takeaways

The shortest path is the minimum-cost route between vertices in a graph.
BFS finds shortest paths in unweighted graphs based on the number of edges.
Dijkstra's algorithm handles weighted graphs with non-negative edge weights.
Bellman-Ford supports negative edge weights and can detect reachable negative cycles.
Floyd-Warshall computes shortest paths between every pair of vertices.
Path reconstruction requires storing predecessor information.
With an adjacency list, BFS typically runs in O(V + E).
Dijkstra with a suitable priority queue typically runs in O((V + E) log V).
Bellman-Ford runs in O(VE).
Floyd-Warshall runs in O(V³).
The graph's weights and the required type of shortest path determine which algorithm should be used.

Topics

Shortest Path Algorithms in Graphs