求最短路径算法

淡淡的烟草味﹌ 2021-06-24 15:57 562阅读 0赞

public static int findPath(int[][] rout, boolean[] visited, int start,                   
                                       int end,  int dist,  int minDist) {
            visited[start - 1] = true;
            for (int i = 1; i < rout[start].length; i++) {
                dist += rout[start][i-1];
                if (i != start && !visited[i-1]) {
                    if (i == end) {
                        if (dist < minDist || minDist == 0){
                            minDist = dist;
                        }
                    }else if(dist < minDist || minDist == 0){
                        minDist = findPath(rout,visited,i,end,dist,minDist);
                    }
                }
                dist -= rout[start][i-1];
            }
            visited[start-1] = false;
            return minDist;
        }

#### rout数组下标第一维从1开始，代表点的坐标，下标为0我预留记录路线图用，第二维代表点与点之间的距离，值为0代表不可达会直接跳过后面的寻址，visited数组用来标记哪些坐标被访问过，防止陷入无限递归中，start代表起点，end代表终点，dist记录当前寻址过的路线长度，minDist记录起点到终点最小路线长度。 ####

#### 核心思想无非两点：1.穷举，2.递归。我在此处有个优化的地方在于当我当前寻址过的路线已经大于已经得出的最小路线长度时候就会跳过这次搜寻过程。若结果minDist=0 那么代表起点无法到达终点。 ####

发表评论取消回复

表情：

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

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

相关阅读

相关 Dijkstra算法求最短路径

定义点node对象 / desc: 路网图中的点 <node>节点</node> @author qts @dat

妖狐艹你老母/ 2024年03月26日 12:00/ 0 赞/ 112 阅读

相关怎么求最短路径

最短路径是指在图中找出一条从起点到终点的路径，使得这条路径的长度最小。常用的算法有 Dijkstra 算法和 Floyd 算法。 Dijkstra 算法是一种贪心算法，它

野性酷女/ 2024年03月25日 19:28/ 0 赞/ 84 阅读

相关最短路径算法

文章目录场景性质和最小支撑树的区别代码实现场景 `给定带权网络

Bertha 。/ 2023年07月18日 14:27/ 0 赞/ 30 阅读

相关最短路径算法

到底是贪心还是动态规划？ Dijkstra算法抽象问题，选择合适的数据结构抽象问题权重图，本质求两节点最小权重值从起点开始遍历所有的临接节点，将节点权重维护

亦凉/ 2023年06月23日 03:00/ 0 赞/ 191 阅读

相关 Dijkstra算法求最短路径

public class Dijk { public static void dijkstra(int v,int[][] f,in

以你之姓@/ 2023年06月17日 07:59/ 0 赞/ 58 阅读

相关最短路径算法

最短路径[算法][Link 1] \include <iostream> void path()\{ //val\[i\]\[j\]从i点到j点的距离，如果

亦凉/ 2022年07月11日 14:09/ 0 赞/ 285 阅读

相关用Floyed算法求最短路径

Floyed算法是可以随便给两个点就可以求出这两个点的最短路径长度以及走法，求单源最短路径可以用Dijkstra（迪杰斯特拉）算法，只要求一个点到其余点的最短距离，只要建一个一

左手的ㄟ右手/ 2022年06月08日 00:36/ 0 赞/ 269 阅读

相关图中求最短路径的算法

在许多应用领域，带权图都被用来描述某个网络，比如通信网络、交通网络等。这种情况下，各边的权重就对应于两点之间通信的成本或交通费用。此时，一类典型的问题就是：在任意

曾经终败给现在/ 2022年04月13日 11:54/ 0 赞/ 320 阅读

相关最短路径算法

1 include <iostream> 2 using namespace std; 3 4 const int INF = 1

古城微笑少年丶/ 2022年01月07日 12:53/ 0 赞/ 648 阅读

相关求最短路径算法

public static int findPath(int[][] rout, boolean[] visited, int start,

淡淡的烟草味﹌/ 2021年06月24日 15:57/ 0 赞/ 563 阅读