图(三,迪杰斯特拉算法)

tar

概述

迪杰斯特拉算法:求图中一个顶点到其他顶点的最短带权路径.
即.单源最短路劲

思路

image.png

上面一张图
我们找到顶点v0到其他顶点的最短带权路径

image.png

假设有两个集合,左边表示已经用过的顶点,右边表示还没走过的顶点
首先将v0放入左边,然后从右边集合中找到v0最近的顶点,放到左边来,依次类推,直到右边集合为空,就可以得到v0到所有结点的一条路径,这条路径就是v0的单源最短路径

步骤

首先用一个boolean[] flag保存已经用过的顶点
int path[]存放前驱结点,int weight[]存放权重,邻接矩阵array表示图,int k表示当前需要处理的顶点
首先,从v0开始

image.png

从邻接矩阵可以得出,v0到v1权重1,到v2权重5,到其他权重I,即:v0到v1最近,于是,我们来处理v1,将v1放到左边集合,以v1为中介点
修改path[],weight[],flag[],k
path[0]=1,
weight[0][j] =max( weight[1][j]+weight[j][1],weight[0][j]),
flag[1] = 1,
k = 1.

然后在右边集合找到距v1最近的点,重复操作.
最后得出path[]和weight[]

代码:

 public static final int I = 100;
    int[][] array=new int[][]{
            {0,1,5,I,I,I,I,I,I},
            {1,0,3,7,5,I,I,I,I},
            {5,3,0,I,1,7,I,I,I},
            {I,7,I,0,2,I,3,I,I},
            {I,5,1,2,0,3,6,I,I},
            {I,I,7,I,3,0,I,5,I},
            {I,I,I,3,6,I,0,2,7},
            {I,I,I,I,9,5,2,0,4},
            {I,I,I,I,I,I,7,4,0}
    };
    public void dijkstar(){
        int k=0;//表示当前正要处理的顶点Vk

        //初始化相关的信息
        int[] path=new int[9];
        int[] weight=array[0];
        //定义一个数组来存放U和V两个集合的信息
        int[] flag=new int[9];
        flag[0]=1;
        //开始逻辑,求VO到某个顶点的最短路径
        for(int v=1;v<9;v++){
            //在能走的路径中找到最短的一条
            int min=I;
            for(int i=0;i<9;i++){
                if(flag[i]==0 && weight[i]<min){
                    k=i;//K为U集合到V集合中找到的顶点
                    min=weight[i];//min找到了最小值的位置
                }
            }
            //从这个最短的路径对应的顶点开始找下一轮
            flag[k]=1;
            //修正当前最短路径
            for(int i=0;i<9;i++){
                //如果经过V顶点的路径比现在的路径短，新更新
                if(flag[i]==0 && (min+array[k][i])<weight[i]){
                    weight[i]=min+array[k][i];//修改路径长度
                    path[i]=k;//保存前驱
                }
            }
        }
        for(int i=0;i<path.length;i++){
            System.out.print(path[i]+" ");
        }
        System.out.println();
        for(int i=0;i<weight.length;i++){
            System.out.print(weight[i]+" ");
        }


        //打印结果
        int v=8;
        while(v!=0){
            System.out.print(path[v]);
            v=path[v];
        }
    }
    @Test
    public void test(){
        dijkstar();
    }