腾讯云

开发者社区

文档建议反馈控制台

首页

文章/答案/技术大牛

发布

社区首页 >问答首页 >寻找最小生成路径的算法？

问寻找最小生成路径的算法？
EN

Stack Overflow用户

提问于 2012-05-23 16:05:20

回答 1查看 2.3K关注 0票数 5

受这个漫画http://xkcd.com/173/的启发

我知道有许多算法可以找到加权图的最小生成树，但是我一直在努力寻找任何能够找到最小生成“路径”的算法。

对于漫画来说，如果我们根据每对关系对每条边进行加权，那么社会最优排列将是最小跨越“路径”，即一条跨越所有顶点的路径。有人能帮忙吗？

graph

graph-algorithm

1元体验云点播

覆盖建站/短视频等热门场景，提供媒资管理、短视频 SDK、小程序插件和播放器云+端一体化能力，助您抓住视频风口

回答 1

Stack Overflow用户

发布于 2012-05-23 16:27:49

寻找最优哈密顿路径(也称为最优路径覆盖)是一个难题。(确定是否存在哈密顿路径是NP-完全问题) 这篇学术文章讨论了一种最优路径覆盖算法。您可以在网上搜索这些术语，以找到其他资源。我不知道有什么现成的代码。

顺便提一句，这个问题 (基本上是你的复制品)清楚地解释了为什么旅行推销员的问题不是开始的地方。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/10729534

复制

Python算法解析：寻找最短路径！

python 路由算法网络原理

最短路径算法用于在图中找到两个节点之间的最短路径。最短路径问题在许多实际应用中都有重要的作用，例如网络路由、导航系统等。

测试开发囤货

2023/08/08

6490

java算法之寻找最小的k个数--1

编程算法

1.快排,不讲了 2.定义一个小根堆,比如priorityqueue,添加数据,利用小根堆每次弹出最小值即可

名字是乱打的

2021/12/22

2610

Prim算法生成最小生成树

基础连接算法

由一个带权值的联通图到一个最小生成树的过程，其实就是从图的所有边中挑出一部分边用来组成树的过程，所以关键在于如何挑选边。

叶茂林

2023/07/30

1920

最短路径生成树与最小生成树

虽然放在一起，但是他们两个除了都是树之外没有一点关系。最短路径生成树，就是ROOT根节点到达任意点距离最短的路径所构成的树，就是最短路径生成树。我画两个图给大家理解。

风骨散人Chiam

2020/10/28

1.1K0

图的最小生成树算法

编程算法

在上一篇文章中，我们看了一下图的遍历算法，主要是对图的深度优先遍历和图的广度优先遍历算法思想的介绍。接下来让我们来看一下图的最小声成树算法。

指点

2019/01/18

2.6K0

最小生成树的Kruskal算法

编程算法

定义：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。[1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。 Kruskal算法简述：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的

用户3577892

2020/06/12

2K0

最小生成树的个数_最小生成树的两种算法

java https 网络安全

设最小生成树的边权之和为 sum，严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

全栈程序员站长

2022/09/22

9800

寻找矩阵中的路径

编程算法

给定一个矩阵和一个字符串，如何从矩阵中寻找出这个字符串在矩阵中的路径？本文就跟大家分享下如何使用回溯法来解决这个问题，欢迎各位感兴趣的开发者阅读本文。

神奇的程序员

2022/04/10

1.1K0

Prim算法-最小生成树

编程算法

基本思想： 1 置S={1} 2 只要S是V的真子集就做如下的贪心选择：　　选取满足条件的i ，i属于S，j输入V-S，且c[i][j]最小的边，并将定点j加入S中　　这个过程直到S==V为止。 3 这个过程所选的边，恰好就是最小生成树算法描述： void Prim(int n,Type * * c) { T = 空集; S = {1}; while(S != V) { (i,j)=i 属于 S 且 j属于V-S的最小权边; T = T∪

用户1154259

2018/01/17

2.6K0

动画演示广度优先算法寻找最短路径

编程算法

上一节，我们刚刚介绍了使用深度优先算法(DFS)解决迷宫问题，这一节我们来介绍广度优先算法(BFS)。BFS 算法与 DFS 十分相似，唯一的区别就是 DFS 算法使用后进先出的栈来保存节点，而 BFS 算法使用先进先出的队列来存储节点，除此之外简直就是一母同胞的亲兄弟。当然，这两种方案各有千秋。DFS 算法找到的路径往往不是最短路径，速度慢但占用内存较少，而 BFS 算法找到的总是最短路径，速度较快但占用内存较多。

用户2870857

2019/12/23

2.1K0

Kruskal算法-最小生成树

编程算法

算法思想： 1 将G的n个顶点看成n个孤立的连通分支，所有的边按权从小到大排序 2 当查看到第k条边时，　　如果断点v和w分别是当前的两个不同的连通分支t1和t2中的顶点时，就用边（v,m）j将t1,t2连接成一个连通分支，然后继续查看第k+1条边；　　如果端点v和w当前的同一个连通分支中，就直接查看第k+1条边实现代码： template <class Type> class EdgeNode{ friend ostream& operator<<(ostream&,EdgeNode<Typ

用户1154259

2018/01/17

2.1K0

☆打卡算法☆LeetCode 64、最小路径和算法解析

编程算法

链接：64. 最小路径和 - 力扣（LeetCode） (leetcode-cn.com)

恬静的小魔龙

2022/08/07

2800

图算法|Prim算法求最小生成树

编程算法 python

01 — 一个实际问题要在n个城市之间铺设光缆，要求有2个：这 n 个城市的任意两个之间都可以通信；铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此要使铺设光缆的总费用最低。如下所示

double

2018/04/02

4K0

最小生成树（Kruskal算法和Prim算法）

编程算法

上一篇文章，我们讲了图的创建和遍历，其中遍历的算法主要有BFS（广度优先算法）和DFS（深度优先算法）两种，并且DFS算法对很多问题都有很好的启示！而今天我们要说一个非常实用的算法——最小生成树的建立！这是图论中一个经典问题，可以使用Kruskal和Prim两种算法来进行实现！

算法工程师之路

2019/08/05

5.3K0

最小生成树算法：Kruskal 与 Prim算法

队列对象集合算法效率

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。

利刃大大

2023/04/12

2K0

Kruscal(最小生成树)算法模版

数据结构编程算法

1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数，m表示边数 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值 5 bool cmp(edge a,edge b) 6 { 7 return a.w<b.w; 8 } 9 int fa[maxn];//因为需要用到并查集来判断两个顶点是否属于同一个连通块 10 int fi

Angel_Kitty

2018/04/09

1.4K0

最小生成树-Prim算法和Kruskal算法

编程算法

Prim算法 1.概览普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算

用户1215536

2018/02/05

3.7K0

最小路径问题 | Dijkstra算法详解（附代码）

编程算法

来源：AI蜗牛车本文共3400字，建议阅读6分钟本文对Dijkstra算法做了一个详细的介绍。一、最短路径问题介绍 1、从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。 2、解决问题的算法：迪杰斯特拉算法（Dijkstra算法）弗洛伊德算法（Floyd算法） SPFA算法这篇文章，就先对Dijkstra算法来做一个详细的介绍~ 二、Dijkstra算介绍算法特点迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路

数据派THU

2022/05/31

5K0

最小生成树(Prim算法和Kruskal算法算法详解)

编程算法

通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离。因为n个节点最少需要n-1个边联通，而距离就需要采取某种策略选择恰当的边。

bigsai

2019/10/21

3.9K0

最小生成树之Prim算法和Kruskal算法

编程算法

一个连通图可能有多棵生成树，而最小生成树是一副连通加权无向图中一颗权值最小的生成树，它可以根据Prim算法和Kruskal算法得出，这两个算法分别从点和边的角度来解决。

业余草

2019/01/21

1.8K0

相似问题

寻找最小瓶颈路径的线性时间算法

算法:寻找最小倍数

用什么算法来寻找最小生成森林？

寻找选定顶点的最小生成树的算法

寻找算法:生成二部图的最小割集

活动推荐

提供大模型在企业的应用构建、高效便捷

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例