Pra*_*dit 32 algorithm shortest-path
任何人都可以告诉我Dijkstra和Prim的算法之间的区别吗？我知道每个算法的作用.但他们看起来和我一样.Dijkstra算法存储最小成本边的总和,而Prim算法存储最多一个最小成本边.这不一样吗？
fer*_*arr 51
Dijsktra算法找到从节点i到所有节点的最小距离(指定i).所以作为回报,你从节点i得到最小距离树.
Prims算法为您提供给定图形的最小spaning树.连接所有节点的树,而所有成本的总和是最小可能的.
因此,使用Dijkstra,你可以以最低的成本从选定的节点转到任何其他节点,你不会得到Prim的
Kev*_*dra 31
我看到的唯一区别是Prim算法存储最小成本边缘,而Dijkstra算法存储从源顶点到当前顶点的总成本.
Dijkstra为您提供从源节点到目标节点的方式,使成本最低.但是,Prim的算法为您提供了最小的生成树,使得所有节点都连接在一起,总成本最低.
简单来说:
所以,如果你想部署火车连接几个城市,你会使用Prim的算法.但如果你想从一个城市到另一个城市尽可能多地节省时间,你就会使用Dijkstra的算法.
Shi*_*hah 22
两者都可以使用完全相同的通用算法实现,如下所示:
Inputs:
G: Graph
s: Starting vertex (any for Prim, source for Dijkstra)
f: a function that takes vertices u and v, returns a number
Generic(G, s, f)
Q = Enqueue all V with key = infinity, parent = null
s.key = 0
While Q is not empty
u = dequeue Q
For each v in adj(u)
if v is in Q and v.key > f(u,v)
v.key = f(u,v)
v.parent = u
对于Prim,传球f = w(u, v)和Dijkstra传球f = u.key + w(u, v).
另一个有趣的事情是,Generic上面也可以实现广度优先搜索(BFS),虽然它会有点过分,因为并不需要昂贵的优先级队列.要将通用算法转换为BFS,f = u.key + 1请将所有权重强制转换为1(即BFS给出从A点到B遍历所需的最小边数).
直觉
这是考虑上面的通用算法的一种好方法:我们从两个桶A和B开始.最初,将所有顶点放在B中,这样桶A就是空的.然后我们将一个顶点从B移动到A.现在查看A中顶点的所有边,这些边穿过B中的顶点.我们使用这些交叉边的一些标准选择一条边并将相应的顶点从B移动到A.重复此过程,直到B为空.
实现这个想法的一种强制方式是维护A中顶点的边缘优先级队列,该顶点跨越到B.显然,如果图形不稀疏,那将是麻烦的.那么问题是我们可以改为保持顶点的优先级队列吗？这实际上我们可以最终决定从B中选择哪个顶点.
历史背景
有趣的是,两种算法背后的技术的通用版本在概念上与1930年一样久,即使电子计算机不在身边.
故事始于OtakarBorůvka,他需要一个家庭朋友的算法,试图找出如何用最低成本的电线连接摩拉维亚(现在是捷克共和国的一部分)的城市.他于1926年在数学相关期刊上发表了他的算法,因为计算机科学当时并不存在.这引起了人们对VojtěchJarník的关注,他想到了Borůvka算法的改进并于1930年发布了.他实际上发现了我们现在所知的Prim算法的算法,他在1957年重新发现了它.
独立于所有这些,在1956年,Dijkstra需要编写一个程序来展示他所研究所开发的新计算机的功能.他认为让电脑找到在荷兰两个城市之间旅行的连接会很酷.他在20分钟内设计了算法.他创建了一个64个城市的图表,其中有一些简化(因为他的计算机是6位),并为这台1956年的计算机编写了代码.然而他没有发表他的算法,因为主要是没有计算机科学期刊,他认为这可能不是很重要.第二年,他了解了连接新计算机终端的问题,使得导线的长度最小化.他想到了这个问题并重新发现了Jarník/ Prim' s算法再次使用与他前一年发现的最短路径算法相同的技术.他提到他的两种算法都是在不使用笔或纸的情况下设计的.1959年,他在一篇长达2.5页的论文中发表了这两种算法.