Graph Shortest Path Algorithms Overview

Beginners do not need to think graph algorithms are hard. They are just extensions of simple algorithm ideas. Once you understand basic tree level-order traversal, you can come up with these algorithms yourself.

Since this is a basic knowledge chapter, I will not provide full code for each algorithm here. The detailed code will be shown in later chapters.

This article focuses on the main ideas, usage scenarios, and how these advanced algorithms connect with basic knowledge. It will help you get a complete understanding of shortest path algorithms on graphs.

Overview of Shortest Path Problems

Shortest path problems are used a lot in real life, for example, to find the minimum cost, shortest distance, or least time.

In algorithms, we usually model these problems as finding the smallest path weight in a weighted graph. In this article, "shortest path" and "minimum path weight sum" mean the same thing.

There are two main types of shortest path problems: "single-source shortest path" and "all-pairs shortest path". Below are some classic algorithms.

Single-source Shortest Path

Single-source shortest path means finding the shortest path from one starting point to all other nodes.

For example, if a graph has n nodes labeled 0, 1, 2, ..., n-1, and you are asked to find the shortest path from node 2 to every other node, this is a single-source shortest path problem.

The output of a single-source shortest path algorithm is usually a one-dimensional array distTo, where distTo[i] means the shortest path length from the start node to node i.

Common single-source shortest path algorithms are:

1. Dijkstra algorithm. It is basically BFS plus a greedy idea. It is efficient, but cannot handle graphs with negative weights.

2. Queue-based Bellman-Ford algorithm. This is also based on BFS. It can handle negative weights, but is slower than Dijkstra.

Point-to-Point Shortest Path

In many algorithm problems, we don't need to find the shortest paths from a start node to all other nodes. We only need to find the shortest path from a start node src to a target node dst. This kind of problem is called a point-to-point shortest path problem.

Usually, the point-to-point shortest path problem can be seen as a special case of the single-source shortest path problem. You can run a single-source shortest path algorithm from src, and stop early when you reach dst.

But there is an algorithm designed just for point-to-point problems: the A* Algorithm (A Star Algorithm).

I often say that the core of algorithms is brute-force search. If you want to make brute-force more efficient, you should use as much information as possible. In point-to-point shortest path problems (where both the start and end are known), you have more information than in single-source shortest path problems (where only the start is known). So, you can use this extra information to make the algorithm faster.

For example, if you know the target is to the lower right of the start, you can guess that searching towards the lower right may reach the target faster.

This is the key idea of the A* algorithm: it makes full use of the known information and searches in a certain direction to find the target faster. This kind of algorithm is called a heuristic search algorithm.

But remember, this guess is only a rule of thumb and is not always correct. For example, the lower right may be a dead end, and you might need to go around to the upper left to reach the target.

So, heuristic algorithms need to set a reasonable heuristic function. You need to balance between the rule of thumb and the real situation to make sure the algorithm is still efficient even if the guess is wrong.

All-Pairs Shortest Path

The all-pairs shortest path problem asks you to find the shortest paths between any two nodes in a graph.

For example, if a graph has n nodes numbered from 0, 1, 2, ..., n-1, you need to find the shortest path between every pair of nodes. This is called the all-pairs shortest path problem.

The final output of an all-pairs shortest path algorithm is a 2D array dist, where dist[i][j] means the shortest path length from node i to node j.

The most famous algorithm for this is the Floyd algorithm, which is actually a dynamic programming algorithm.

In theory, you can run a single-source shortest path algorithm for every node to solve this problem.

But in practice, you should choose the algorithm based on the graph’s structure. Sometimes, using Floyd is more efficient. Other times, running Dijkstra multiple times is better. You will understand this when we talk about the complexity of these algorithms later.

The Effect of Negative Weight Edges

When finding the shortest path, you must pay attention to whether the graph has negative weight edges. If it does, you must check for negative weight cycles.

Why do negative weight edges matter? Because they make the problem more complicated. Here’s a simple example to help you understand:

Suppose you are at the starting node s. There are two neighbors: a and b. The edge s->a has weight 3, and s->b has weight 4.

If there are no negative weight edges, then it's clear that the shortest path from s to a is just s->a, with a total weight of 3. If you go from s to b first, and then to a, the total weight will be at least 4 or more—never less than 3.

But if there is a negative weight edge, things change. For example, if the edge b->a has weight -10, then the path s->b->a has a total weight of -6, which is much less than 3.

For algorithms like Dijkstra that use a greedy strategy, there is an important assumption: the total path weight always increases as you use more edges. Negative weight edges break this assumption, and the algorithm fails.

If the graph has a negative weight cycle, the shortest path problem has no meaning. For example, if there is a negative weight cycle on the path from s to a, you could keep going around the cycle forever, making the total path weight smaller and smaller.

Among common shortest path algorithms, Dijkstra and A* cannot handle negative weight edges. Floyd and Bellman-Ford can handle negative weights, and Bellman-Ford is often used to detect negative weight cycles.

Next, let’s look at the core ideas of these algorithms.

Introduction to Dijkstra's Algorithm

Introduction to A* Algorithm

Introduction to Bellman-Ford/SPFA Algorithm

Introduction to Floyd's Algorithm