Java 最短路径算法代码错误修复

**原代码:**javaimport java.util.Arrays;

public class ShortestPathSolution {

static final int RED = 2;    static final int GREEN = 1;    static final int WHITE = 0;

public int[] findAllShortestPath(int n, int[][] edges, int src) {        int[] dist = new int[n + 1];         Arrays.fill(dist, Integer.MAX_VALUE);        int[] visit = new int[n + 1];

    visit[src] = GREEN;        dist[src] = 0;

    for (int i = 0; i < n; i++) {            int s = 0;            for (int j = 1; j <= n; j++) {                if (visit[j] == GREEN && (s == 0 || dist[j] < dist[s]))                     s = j;            }            if (s == 0) break;                        visit[s] = RED;

        for (int[] ed : edges) {                int u = ed[0], v = ed[1], w = ed[2];

            if (s == u && visit[v] != RED) {                    int d = dist[s] + w;

                if (d < dist[v]) {                        dist[v] = d;                        visit[v] = GREEN;                    }                }            }        }

    System.out.println('所有的顶点路径信息:');        for (int i = 1; i <= n; i++)             System.out.println('目标顶点 ' + i + ' -> ' + dist[i]);        return dist;    }}

代码问题:

原程序中的循环次数为 n，而实际上对于一个包含 n 个节点的图，最短路径最多经过 n-1 条边。因此，循环次数应该为 n-1。

**修改后的代码:**javaimport java.util.Arrays;

public class ShortestPathSolution {

static final int RED = 2;    static final int GREEN = 1;    static final int WHITE = 0;

public int[] findAllShortestPath(int n, int[][] edges, int src) {        int[] dist = new int[n + 1];         Arrays.fill(dist, Integer.MAX_VALUE);        int[] visit = new int[n + 1];

    visit[src] = GREEN;        dist[src] = 0;

    for (int i = 0; i < n - 1; i++) { // 修改循环次数，应为n-1            int s = 0;            for (int j = 1; j <= n; j++) {                if (visit[j] == GREEN && (s == 0 || dist[j] < dist[s]))                     s = j;            }            if (s == 0) break;                        visit[s] = RED;

        for (int[] ed : edges) {                int u = ed[0], v = ed[1], w = ed[2];

            if (s == u && visit[v] != RED) {                    int d = dist[s] + w;

                if (d < dist[v]) {                        dist[v] = d;                        visit[v] = GREEN;                    }                }            }        }

    System.out.println('所有的顶点路径信息:');        for (int i = 1; i <= n; i++)             System.out.println('目标顶点 ' + i + ' -> ' + dist[i]);        return dist;