无向图的最短路径（Java）

1. 迪杰斯特拉算法求解图的最短路径

import java.util.Arrays;

import static main.Common.INF;

public class Dijkstra {

    private int[][] path;
    
    private int vertex;
    
    public Dijkstra(int nodeNum, String[] src) {
        path = new int[nodeNum][nodeNum];
        for(int i = 0;i < nodeNum;i++) {
            for(int j = 0;j < nodeNum;j++) {
                path[i][j] = INF;
            }
        }

        this.vertex = src.length;
        for(String str : src) {
           int[] data = Arrays.stream(str.split(" ")).mapToInt(Integer::parseInt).toArray();
           path[data[0]][data[1]] = data[2];
           path[data[1]][data[0]] = data[2];
        }
    }

    /**
     *
     * @param vs 起始顶点
     */
    public int[] process(int vs) {

        int[] prev = new int[vertex];
        int[] dist = new int[vertex];
        boolean[] find = new boolean[vertex];

        //初始化
        for (int i = 0; i < vertex; i++) {
            find[i] = false;          // 顶点i的最短路径还没获取到。
            prev[i] = 0;              // 顶点i的前驱顶点为0。
            dist[i] = path[vs][i];  // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
        }

        // 对"顶点vs"自身进行初始化
        find[vs] = true;
        dist[vs] = 0;

        // 遍历mVexs.length-1次；每次找出一个顶点的最短路径。
        int k=0;
        for (int i = 1; i < vertex; i++) {
            // 寻找当前最小的路径；
            // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
            int min = INF;
            for (int j = 0; j < vertex; j++) {
                if (find[j]==false && dist[j]<min) {
                    min = dist[j];
                    k = j;
                }
            }
            // 标记"顶点k"为已经获取到最短路径
            find[k] = true;

            // 修正当前最短路径和前驱顶点
            // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
            for (int j = 0; j < vertex; j++) {
                int tmp = (path[k][j]==INF ? INF : (min + path[k][j]));
                if (find[j]==false && (tmp<dist[j]) ) {
                    dist[j] = tmp;
                    prev[j] = k;
                }
            }
        }

        return dist;
    }
}

2. 弗洛伊德算法求解无向连通图的最小环

import java.util.Scanner;

//无向图的最小环
public class Floyd {

    private int[][] edge;

    private int[][] dist;

    private int node;

    public Floyd(int n) {
        this.node = n;
        dist = new int[n + 1][n + 1];
        edge = new int[n + 1][n + 1];
        for(int i = 1;i <= n;i++)
            for (int j = 1; j <= n; j++) {
                if(i == j)
                    edge[i][j] = 0;
                else
                    edge[i][j] = Common.INF;
            }
    }

    /**
     *
     * @param m
     * @param input 通过input得到两个点及其距离
     */
    public void init(int m, Scanner input) {
        for(int i = 1;i <= m;i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int dis = input.nextInt();
            if(edge[a][b] > dis) {
                edge[a][b] = dis;
                edge[b][a] = dis;
            }
        }
    }

    public int process() {
        int minCircle = Common.INF;
        for(int i = 1 ; i <= node ; ++i) {
            for (int j = 1; j <= node; ++j)
                dist[i][j] = edge[i][j];
        }

        //根据Floyd的原理，在最外层循环做了k-1次之后，dis[i][j]则代表了i到j的路径中所有结点编号都小于k的最短路径
        for(int k = 1;k <= node;k++) {

            //环的最小长度为edge[i][k]+edge[k][j]+i->j的路径中所有编号小于k的最短路径长度
            for(int i = 1;i < k;i++) {
                for(int j = i + 1;j < k;j++) {
                    if(dist[i][j] + edge[i][k] + edge[k][j] < Common.INF) {
                        minCircle = Math.min(minCircle, dist[i][j] + edge[j][k] + edge[k][i]);
                    }
                }
            }

            //floyd原来的部分,更新dist[i][j]
            for(int i = 1 ; i <= node ; ++i){
                for(int j = 1 ; j <= node ; ++j){
                    if(dist[i][j] > dist[i][k] + dist[k][j]){
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        return minCircle;
    }
}