如何实现最短路径算法？Bellman-Ford算法实现

最短路径算法是指在一个有向加权图中，找出从起点到终点的最短路径。常见的解决方案有两种：Dijkstra算法和Bellman-Ford算法。

Bellman-Ford算法

Bellman-Ford算法是一种动态规划算法，它通过逐步增加路径长度的限制，来逐步缩小最短路径的范围。在每次更新时，对所有的边进行松弛操作，更新它们到起点的距离值。如果在第$n$次更新时，仍然存在松弛的情况，则说明存在负环，没有最短路径。

下面是Bellman-Ford算法的Java实现：

public class BellmanFord {
    public static int shortestPath(int[][] graph, int source, int target) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int u = 0; u < n; u++) {
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] != 0) {
                        int newDist = dist[u] + graph[u][v];
                        if (newDist < dist[v]) {
                            dist[v] = newDist;
                        }
                    }
                }
            }
        }
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        return -1;
                    }
                }
            }
        }
        return dist[target];
    }
}