求最短路径算法

淡淡的烟草味﹌ 2021-06-24 15:57 514阅读 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 条评论，514人围观）

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

相关阅读

相关最短路径算法

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

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

相关最短路径解决算法

> 一.问题引入 > > 问题：从某顶点出发，沿图的边到达另一顶点（O(n2)Xn个，总体为3次方）所经过的路 > > 径中，各边上权值之和最小的一条路径—

蔚落/ 2022年08月20日 13:12/ 0 赞/ 242 阅读

相关最短路径算法

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

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

相关用Floyed算法求最短路径

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

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

相关最短路径算法实现

什么是最短路径呢？考虑到带权路径图，我们把一条路径上经过的权值之和是该路径的路径长度或者是带权路径长度。那么我来个案例，比如我们还是村庄之间修路，我们指定了一个村庄起点和

妖狐艹你老母/ 2022年06月03日 02:58/ 0 赞/ 304 阅读

相关求三角形的最短路径

![这里写图片描述][70] import java.util.; public class Solution { //(1)不考虑

ゝ一世哀愁。/ 2022年05月20日 07:26/ 0 赞/ 281 阅读

相关最短路径—Floyd算法

Floyd算法： 1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w

冷不防/ 2022年05月12日 05:50/ 0 赞/ 283 阅读

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

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

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

相关最短路径算法

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

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

相关求最短路径算法

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

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