算法--单源最短路径

2023-11-15

字数统计: 766字 | 阅读时长≈ 3分

Dijkstra：只能处理正边

不适用情况：存在负权边
算法步骤：
- 初始化：起点最短路劲为0，其余为无穷大
- 每次从未访问顶点中选择一个路劲值最短的顶点
- 更新与该顶点相连的顶点的最短路劲
- 重复2，3直到所有顶点都访问过

/**
 * Dijkstra单源最短路劲
 * @param n 顶点个数
 * @param edges 边权集 {{from,to,weight}}
 * @param start 起点
 */
public void dijkstra(int n,int[][] edges,int start){
    int[] res=new int[n];//保存最短路劲值
    boolean[] isVisit=new boolean[n];//记录顶点是否已访问
    //初始化：起点为0，其他为∞
    res[start]=0;
    for (int i = 0; i < n; i++) {
        if (i!=start) {
            res[i] = Integer.MAX_VALUE;
        }
    }

    while (true) {
        //选取未访问中最小的一个顶点
        int vertex=-1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (!isVisit[i] && res[i] < min) {
                min = res[i];
                vertex = i;
            }
        }
        //所有顶点被访问，结束循环
        if (vertex==-1){
            break;
        }
        //更新顶点邻居值
        for (int[] edge : edges) {
            int from = edge[0];
            int end = edge[1];
            int weight = edge[2];
            if (from == vertex && res[vertex] + weight<res[end]) {
                res[end] = res[vertex] + weight;
            }
        }
        //标记顶点被访问
        isVisit[vertex] = true;
    }
}

Bellman-Ford：可以处理负边，但不能处理负环

不适用情况：存在负环
算法步骤：
- 初始化：起点最短路劲为0，其余为无穷大
- 循环顶点个数-1次：每次循环，遍历所有边，如果终点最短路劲值大于起点最短路劲值+该边权值，则更新终点最短路劲值

/**
 * Bellman-Ford单源最短路劲
 * @param n 顶点个数
 * @param edges 边权集 {{from,to,weight}}
 * @param start 起点
 */
public void bellman(int n,int[][] edges,int start){
    int[] res=new int[n];//保存最短路劲值
    //初始化：起点为0，其他为∞
    res[start]=0;
    for (int i = 0; i < n; i++) {
        if (i!=start) {
            res[i] = Integer.MAX_VALUE;
        }
    }
    //顶点个数-1轮：每轮更新边到顶点的最短路劲值
    for (int i = 0; i < n - 1; i++) {
        for (int[] edge : edges) {
            int from=edge[0];
            int end=edge[1];
            int weight=edge[2];
            if (res[from]!=Integer.MAX_VALUE && res[from] + weight < res[end]){//起点为∞时，不更新
                res[end]=res[from]+weight;
            }
        }
    }

    //多一轮：检测负环
    for (int[] edge : edges) {
        int from = edge[0];
        int end = edge[1];
        int weight = edge[2];
        //进入if则说明存在负环
        if (res[from]!=Integer.MAX_VALUE && res[from] + weight < res[end]) {
            System.out.println("图中存在负权环");
            return;
        }
    }

}

在Bellman-Ford算法中，可以通过一轮额外的松弛操作来检测负环。在进行顶点个数-1轮的基本算法操作后，再进行一轮额外的松弛操作。如果在这轮松弛操作中，仍然存在顶点的最短路径值发生改变，则说明存在负环。因为在没有负环的情况下，进行n-1轮松弛操作可以得到最短路径值，如果仍然存在顶点的最短路径值发生改变，说明存在负环。

本文作者： zzr
本文链接： http://zzruei.github.io/2023/11a33f222a.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！