蓝桥-最短路径2-Dijstra

妖狐艹你老母 2022-07-12 02:50 226阅读 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[]标记是否最短。*/

发表评论取消回复

表情：

评论列表（有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯：路径

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由 20

小咪咪/ 2024年03月25日 22:48/ 0 赞/ 131 阅读

相关最小生成树（prim）和最短路径（dijstra）

两个著名的贪心算法对比两个算法（这里讨论均为无向图）相同点：无疑都是将顶点划分为s集合和v-s集合，首先都将源点加入到s集合，其余结点在v-s集合中。接着找加入到s集合

川长思鸟来/ 2023年06月09日 14:25/ 0 赞/ 40 阅读

相关最短路径问题（最短路径）

最短路径问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

Love The Way You Lie/ 2022年08月01日 14:48/ 0 赞/ 388 阅读

相关蓝桥-最短路径3-Bellman-Ford

package com.jkxy.photoDeep; public class BellmanFord { static int u[]={

川长思鸟来/ 2022年07月12日 03:06/ 0 赞/ 231 阅读

相关蓝桥-最短路径2-Dijstra

package com.jkxy.photoDeep; public class Dijkstra { static int e[][] = {

妖狐艹你老母/ 2022年07月12日 02:50/ 0 赞/ 227 阅读

相关蓝桥-最短路径1-warshall

package com.jkxy.photoDeep; public class warshall { static int k,i,j;

╰+哭是因爲堅強的太久メ/ 2022年07月12日 02:50/ 0 赞/ 225 阅读

相关蓝桥-最短路径2-Dijstra

package com.jkxy.photoDeep; public class Dijkstra { static int e[][] = {

Bertha 。/ 2022年07月12日 02:50/ 0 赞/ 216 阅读

相关蓝桥-最短路径1-warshall

package com.jkxy.photoDeep; public class warshall { static int k,i,j;

谁借莪１个温暖的怀抱￠/ 2022年07月12日 02:50/ 0 赞/ 180 阅读

相关蓝桥-图3-深度优先遍历-地图最短路径

package com.jkxy.photo; public class CityDeepTraverse { static int[][]

刺骨的言语ヽ痛彻心扉/ 2022年07月12日 01:10/ 0 赞/ 217 阅读

相关蓝桥杯国赛——路径（最短路）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

水深无声/ 2021年07月17日 01:34/ 0 赞/ 596 阅读