Graph Shortest Path Algorithms Overview

Beginner should not think graph algorithms are hard. They come from simple algorithm ideas. If you can master basic binary tree level order traversal, you can also invent these algorithms. They are not a big deal.

Since this is the basics chapter, this article will not explain the full code of each algorithm. The detailed implementations will be in future chapters.

The focus here is to explain key ideas, use cases, and how these advanced algorithms relate to basic knowledge. This will help beginners build an overall understanding of shortest path algorithms in graphs.

Overview of Shortest Path Problems

Shortest path problems are widely used in real life, such as finding the lowest cost, shortest distance, or least time.

In algorithms, we usually turn these problems into finding the minimum path weight in a weighted graph. To make it simple, in this article, "shortest path" and "minimum path weight sum" mean the same thing.

Shortest path problems can be divided into "single-source shortest path" and "all-pairs shortest path". We will introduce a few classic algorithms.

Single-Source Shortest Path

Single-source shortest path means finding the shortest path from a starting node to all other nodes.

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

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

Sometimes, you don't need to find the shortest path to all nodes, but only from a start node src to a target node dst. This is a special case of the single-source shortest path problem.

Classic algorithms for single-source shortest path include:

1. Dijkstra algorithm. It is basically BFS + greedy. It is efficient, but it cannot handle graphs with negative weights.

2. Queue-based Bellman-Ford algorithm. It is also based on BFS. It can handle graphs with negative weights, but is slower than Dijkstra 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