Graph Shortest Path Algorithms Overview

Beginners should not think that graph algorithms are very difficult. They are all extensions of simple algorithm ideas. If you fully understand basic level-order traversal of binary trees, you could even invent these algorithms yourself. There's nothing mysterious about them.

Since we are currently in the basics section, this article will not go into the full code implementation of each algorithm. Detailed code will be covered in later chapters.

This article focuses on the key principles of these algorithms, their application scenarios, and how these advanced algorithms connect to the basic knowledge. The goal is to help beginners gain an overall understanding of shortest path algorithms in graph structures.

Overview of Shortest Path Problems

Shortest path problems are widely used in real life, such as calculating minimum cost, shortest distance, or least time.

In algorithms, we often abstract these problems into finding the minimum path weight in a weighted graph. For simplicity, in this article, "shortest path" and "minimum path weight sum" mean the same thing.

Shortest path problems are generally divided into "single source shortest path" and "all pairs shortest path". Below, we introduce several classic algorithms.

Single Source Shortest Path

The single source shortest path problem asks you to calculate the shortest paths from a starting point to all other vertices in the graph.

For example, if a graph has n nodes labeled 0, 1, 2, ..., n-1, and you're asked to find the shortest paths from node 2 to all other nodes, that's a single source shortest path problem.

The output of a single source shortest path algorithm is typically a one-dimensional array distTo, where distTo[i] represents the shortest path length from the starting point to node i.

In many algorithm problems, we don't need to compute the shortest path from the start to every other node—just from a start node src to a target node dst. These problems are a special case of the single source shortest path problem.

Representative single source shortest path algorithms include:

1. Dijkstra's algorithm, which is essentially BFS plus a greedy strategy. It is efficient, but cannot handle graphs with negative edge weights.

2. The queue-based Bellman-Ford algorithm, which is also essentially based on BFS, can handle negative edge weights, but is less efficient than Dijkstra's algorithm.

All-Pairs Shortest Path

The all-pairs shortest path problem asks you to compute the shortest path between every pair of vertices in a graph.

Suppose a graph has n nodes, numbered 0, 1, 2, ..., n-1. If you are asked to compute the shortest path between all pairs of nodes, this is the all-pairs shortest path problem.

The output of all-pairs shortest path algorithms is usually a two-dimensional array dist, where dist[i][j] represents the length of the shortest path from node i to node j.

The most representative algorithm for this is the Floyd algorithm, which is essentially a dynamic programming approach.

In theory, you can run a single-source shortest path algorithm from every node to get the all-pairs shortest path solution.

However, in practice, you should choose the method based on the structure of the graph. Sometimes, using the Floyd algorithm is more efficient; in other cases, repeatedly using a single-source algorithm like Dijkstra is faster. Once we discuss the complexity of these algorithms, you will understand the difference.

The Effect of Negative Weight Edges

When calculating shortest paths, it is important to check whether the graph contains negative weight edges.

For example, Dijkstra's algorithm for single-source shortest path cannot handle graphs with negative weight edges, while the Bellman-Ford algorithm can handle negative weights but is less efficient than Dijkstra. For the all-pairs shortest path, the Floyd algorithm can handle negative weight edges.

Why do negative weight edges affect shortest path algorithms? Because they make the problem more complicated. Let’s look at a simple example to understand this:

Suppose you are at the starting point s, which is connected to nodes a and b. The edge s->a has weight 3, and s->b has weight 4.

If there are no negative weight edges in the graph, then you can be sure that the shortest path from s to a is s->a, with a total weight of 3. Any path from s to a via b must have a weight greater than 4, so it cannot be shorter than 3.

But if the graph contains negative weight edges, the situation changes. For example, if the edge b->a has a weight of -10, then the path s->b->a has a total weight of -6, which is even less than the direct path s->a with weight 3.

For algorithms like Dijkstra, which rely on greedy ideas, there is an important assumption: as you add more edges to a path, the total weight should only increase. The presence of negative weight edges breaks this assumption, causing the algorithm to fail.

Therefore, when greedy methods cannot be used, the efficiency of the algorithm usually decreases.

Next, we will introduce the core principles of several classic single-source shortest path algorithms.

Introduction to Dijkstra's Algorithm

Introduction to Bellman-Ford/SPFA Algorithm

Introduction to the Floyd Algorithm