2022.3.28学习日记

今天实现Java的迪杰斯特拉算法

public static int Di(int [][]G,int v0,int v1) {//G为二维数组，v0是起始点,v1是终点
        
        int n=G.length;
        boolean S[]=new boolean[n];//收集起点到目标点是否可通
        int D[]=new int[n];//存放到目标点距离
        int path[]=new int[n];//存放目标点到起点的经过前驱
        int v=0;
        for(v=0;v) {
            S[v]=false;
            D[v]=G[v0][v];
            if(D[v]<top){
                path[v]=0;
            }
            else {
                path[v]=-1;
            }
        }
        S[v0]=true;
        D[v0]=0;
        //以上初始化完成接下来开始计算数据
        v=0;
        for(int i=1;i) {
            int min=top;
            for(int w=0;w) {
                if(!S[w]&&D[w]<min) {
                    v=w;
                    min=D[w];
                }
            }
            S[v]=true;
            for(int w=0;w) {
                if(!S[w]&&(D[v]+G[v][w]<D[w])) {
                    D[w]=D[v]+G[v][w];
                    path[w]=v;
                }
            }
        }
        return D[v1-1];
    }