非递归Floyd-Warshall路径重构：next矩阵与打印机制解析

Let's break down exactly what the next matrix does here, and how the non-recursive path reconstruction works—this is a slightly different take on the standard Floyd-Warshall path tracking, so it makes sense to clarify!

What Does the next Matrix Represent? #

Unlike the more common definition where next[i][j] stores the predecessor of j on the shortest path from i, this implementation uses next[i][j] to store the immediate next node you should visit after i to reach j via the shortest path.

Let's start with the initialization to make this concrete:

int[][] next = new int[numVertices][numVertices];
for (int i = 0; i < next.length; i++) {
    for (int j = 0; j < next.length; j++)
        if (i != j) next[i][j] = j + 1;
}

Since the input uses 1-indexed nodes but the array is 0-indexed, we initialize next[i][j] to j+1 when i≠j. This means: initially, the shortest path from node i+1 to j+1 is assumed to be direct—so the next node after i+1 is just j+1.

Then during the Floyd-Warshall relaxation step:

if (dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    next[i][j] = next[i][k];
}

When we find a shorter path from i to j through intermediate node k, we update next[i][j] to match next[i][k]. In plain language: "To get from i to j via the shortest path, first go to whatever node you'd start with to get from i to k." This chains together the path step-by-step.

How the Non-Recursive Path Printing Works #

The printResult method builds the path by following these next pointers until we reach the destination. Let's walk through the code line by line:

int u = i + 1;
int v = j + 1;
String path = format("%d -> %d %2d %s", u, v, (int) dist[i][j], u);
do {
    u = next[u - 1][v - 1];
    path += " -> " + u;
} while (u != v);

Here's the play-by-play:

1. We start with u as the starting node (i+1) and v as the destination node (j+1).
2. We initialize the path string with the starting node and the distance.
3. We enter a loop where we update u to next[u-1][v-1] (converting back to 0-index for the array). This gives us the next node we need to visit from our current u to reach v.
4. We append this new node to the path string.
5. We repeat until u equals v—meaning we've arrived at the destination.

Quick Example #

Take the shortest path from node 1 to node 4 in the sample input: the algorithm finds the path 1 -> 3 -> 4 (total distance 0). Here's how the next matrix guides this:

• next[0][3] (for 1→4) is set to next[0][2] (for 1→3), which is 3. So first step: from 1, go to 3.
• Then we check next[2][3] (for 3→4), which is 4. We add 4 to the path, and since u now equals v, we stop.

This gives us the full path 1 -> 3 -> 4.

Why This Approach Works #

This "next node" definition is a valid alternative to the predecessor-based method. The biggest upside here is that path reconstruction is simple and iterative—no recursion required. You just keep following the next pointer from your current node until you hit the destination, which avoids potential stack overflow issues with deep recursion for large graphs.

内容的提问来源于stack exchange，提问作者user7826451