蓝桥-最短路径2-Dijstra

Bertha 。 2022-07-12 02:50 123阅读 0赞

package com.jkxy.photoDeep;
    public class Dijkstra {
        static int e[][] = { { 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 1, 12, 99999, 99999, 99999 },
                { 0, 99999, 0, 9, 3, 99999, 99999 },
                { 0, 99999, 99999, 0, 99999, 5, 99999 },
                { 0, 99999, 99999, 4, 0, 13, 15 },
                { 0, 99999, 99999, 99999, 99999, 0, 4 },
                { 0, 99999, 99999, 99999, 99999, 99999, 0 } };
        static int v, i, j, min = 99999;
        static int u;// 行中dis最小
        static int dis[] = { 0, 0, 1, 12, 99999, 99999, 99999 };
        static int book[] = { 0, 1, 0, 0, 0, 0, 0 };
        public static void main(String[] args) {
            for (v = 1; v <= 5; v++) {
                min=99999;
                //找出距离顶点1最近的点
                for (i = 1; i <= 6; i++) {
                    if (book[i] == 0 && dis[i] < min) {
                        min = dis[i];
                        u = i;
                    }
                }
                //找到后，标记此点已确定最短，（1-？）<(1-最近点-？)松弛
                book[u] = 1;
                for (j = 1; j <= 6; j++) {
                    if(e[u][j]<99999){
                        if (dis[u] + e[u][j] < dis[j]) {
                            dis[j] = dis[u] + e[u][j];
                        }
                    }
                }
            }
            for(i=1;i<=6;i++){
                System.out.print(dis[i]+"/");
            }
        }
    
    }
    /*Dijstra单点多源：循环对起点1距离最近的点（确定点越来越多）松弛。 （1-？）<(1-最近点-？) 实现：先定义路径对应二维数组，定义dis[]用以记录起点1到各顶点距离。 定义book[]标记是否最短。*/