作业帮Dijkstra算法的堆优化不要代码.要打字……是把dist作为关键字建堆么,一开始堆头是dist[s]=0,其余全是maxlongint,然后按dijkstra的思想搞么?但是这样取出一个元素,最坏情况下要堆其他n个元素进行调
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 23:19:48
![Dijkstra算法的堆优化不要代码.要打字……是把dist作为关键字建堆么,一开始堆头是dist[s]=0,其余全是maxlongint,然后按dijkstra的思想搞么?但是这样取出一个元素,最坏情况下要堆其他n个元素进行调](/uploads/image/z/6841312-16-2.jpg?t=Dijkstra%E7%AE%97%E6%B3%95%E7%9A%84%E5%A0%86%E4%BC%98%E5%8C%96%E4%B8%8D%E8%A6%81%E4%BB%A3%E7%A0%81.%E8%A6%81%E6%89%93%E5%AD%97%E2%80%A6%E2%80%A6%E6%98%AF%E6%8A%8Adist%E4%BD%9C%E4%B8%BA%E5%85%B3%E9%94%AE%E5%AD%97%E5%BB%BA%E5%A0%86%E4%B9%88%2C%E4%B8%80%E5%BC%80%E5%A7%8B%E5%A0%86%E5%A4%B4%E6%98%AFdist%5Bs%5D%3D0%2C%E5%85%B6%E4%BD%99%E5%85%A8%E6%98%AFmaxlongint%2C%E7%84%B6%E5%90%8E%E6%8C%89dijkstra%E7%9A%84%E6%80%9D%E6%83%B3%E6%90%9E%E4%B9%88%3F%E4%BD%86%E6%98%AF%E8%BF%99%E6%A0%B7%E5%8F%96%E5%87%BA%E4%B8%80%E4%B8%AA%E5%85%83%E7%B4%A0%2C%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%E4%B8%8B%E8%A6%81%E5%A0%86%E5%85%B6%E4%BB%96n%E4%B8%AA%E5%85%83%E7%B4%A0%E8%BF%9B%E8%A1%8C%E8%B0%83)
Dijkstra算法的堆优化不要代码.要打字……是把dist作为关键字建堆么,一开始堆头是dist[s]=0,其余全是maxlongint,然后按dijkstra的思想搞么?但是这样取出一个元素,最坏情况下要堆其他n个元素进行调
Dijkstra算法的堆优化
不要代码.要打字……
是把dist作为关键字建堆么,一开始堆头是dist[s]=0,其余全是maxlongint,然后按dijkstra的思想搞么?但是这样取出一个元素,最坏情况下要堆其他n个元素进行调整,每次都是logn,这样的话不就退化成O(n*n*logn)了么?求到底怎么优化……
Dijkstra算法的堆优化不要代码.要打字……是把dist作为关键字建堆么,一开始堆头是dist[s]=0,其余全是maxlongint,然后按dijkstra的思想搞么?但是这样取出一个元素,最坏情况下要堆其他n个元素进行调
>>全国交通咨询?
作为一个OIer、我表示对最短路径算法稍有研究.
Dijkstra和Floyd是按需要来看的
首先
dijkstra求的是从一个节点到其他节点的最短路 时间复杂度不优化的情况下是n方
Floyd求的是任意两点间的最短路径、时间复杂度永远是n的立方、而且我表示除了邻接矩阵我再没用其他数据结构写过.
所以在处理很多的结点很多边的时候、Floyd又耗费时间又浪费空间、没有特殊需要不要用.
至于dijkstra、在稀疏图里它一定比SPFA快
>>SPFA是另一种最短路算法、是Bellman-Ford的队列优化
但是对于稠密图、SPFA要比dijkstra快很多.
但是、dijkstra可以用堆优化
用小根堆来维护dijkstra中的dist数组、在每次取最小值的时候取堆顶元素
这样时间复杂度是nlogn级、很快
至于SPFA跟Heapdijkstra哪个快这个不大好比较= =、
OTZ回答的有点跑偏了.
注意最开始的那几行
我强烈推荐dijkstra、Floyd如果不求任意两点的最短路径的话根本没必要.