Java使用SPFA算法最短路问题

SPFA算法（Shortest Path Faster Algorithm）是一种用于解决最短路问题的算法。它是一种单源最短路径算法，可以解决带有负权边的图的最短路径问题。

SPFA算法基本思想是使用队列对图中的所有节点进行遍历，对于每一个节点，如果它的邻居节点的最短路径可以通过当前节点更新，则将邻居节点加入队列中进行下一轮遍历，直到所有节点的最短路径都被更新后停止遍历。

在Java中，可以使用邻接矩阵或邻接表来表示图，并使用队列来实现SPFA算法。下面是一个使用邻接矩阵实现SPFA算法的Java代码示例：

import java.util.*;

public class SPFA {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 5, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, 0, 7, 1, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 4, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 3},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };
        int[] dist = shortestPath(graph, 0);
        System.out.println(Arrays.toString(dist));
    }
    
    public static int[] shortestPath(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        boolean[] inQueue = new boolean[n];
        inQueue[start] = true;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != Integer.MAX_VALUE && dist[v] > dist[u] + graph[u][v]) {
                    dist[v] = dist[u] + graph[u][v];
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        return dist;
    }
}

在上面的代码中，我们使用一个二维数组`graph`来表示图，其中`graph[i][j]`表示从节点`i`到节点`j`的边的权重，如果没有边则为`Integer.MAX_VALUE`。函数`shortestPath`接受一个图和一个起点`start`，返回一个数组`dist`，其中`dist[i]`表示从起点`start`到节点`i`的最短路径。

在函数中，我们首先初始化`dist`数组为`Integer.MAX_VALUE`，表示所有节点到起点的距离都是无限大。然后将起点`start`加入队列中，并标记为已加入队列。进入循环后，每次取出队列中的一个节点`u`，将`u`标记为未加入队列，然后遍历`u`的所有邻居节点`v`，如果从起点到`v`的距离可以通过从起点到`u`再加上`u`到`v`的距离来更新，则更新`dist[v]`的值，并将`v`加入队列中，并标记为已加入队列。当队列为空时，所有节点的最短路径都已被更新，函数返回`dist`数组。