dijkstra算法时间复杂度

A. 最短路问题用Dijkstra算法好还是用遗传算法好

dijkstra适合稠密图，时间复杂度为n^2 或者nlogn+E(堆优化)，但必须保证边权都为正
spfa 适合稀疏图，时间复杂度为kE (k为平均每点连接的边数)

B. johnson算法是什么

Johnson算法适用于求All
Pairs
Shortest
Path.
Johnson算法应用了重标号技术，先进行一次Bellman-Ford算法，然后对原图进行重标号，w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra，每次Dijkstra的复杂度为O(nlogn+m)，于是算法复杂度为O(n^2logn+m)。
关于求解流水作业调度问题的
Johnson
算法具体描述:

C. Dijkstra算法的堆优化

>>全国交通咨询？
作为一个OIer、我表示对最短路径算法稍有研究。
Dijkstra和Floyd是按需要来看的
首先
dijkstra求的是从一个节点到其他节点的最短路 时间复杂度不优化的情况下是n方
Floyd求的是任意两点间的最短路径、时间复杂度永远是n的立方、而且我表示除了邻接矩阵我再没用其他数据结构写过。
所以在处理很多的结点很多边的时候、Floyd又耗费时间又浪费空间、没有特殊需要不要用。
至于dijkstra、在稀疏图里它一定比SPFA快
>>SPFA是另一种最短路算法、是Bellman-Ford的队列优化
但是对于稠密图、SPFA要比dijkstra快很多。
但是、dijkstra可以用堆优化
用小根堆来维护dijkstra中的dist数组、在每次取最小值的时候取堆顶元素
这样时间复杂度是nlogn级、很快
至于SPFA跟Heapdijkstra哪个快这个不大好比较= =、

OTZ回答的有点跑偏了。
注意最开始的那几行
我强烈推荐dijkstra、Floyd如果不求任意两点的最短路径的话根本没必要。

D. 数据结构之图：求所有节点之间的最短路径，用什么算法时间复杂度小求答案与解释

两者时间复杂度一般都是O(n3)，但对于稀疏图来说重复使用Dijkstra方法比较好！
Dijkstra算法时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂
度变为0（v*lgn）。
源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。
当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
具体详细解释你可以看看这个http://blog.chinaunix.net/uid-27164517-id-3287891.html。

E. 请教Dijkstra算法的时间复杂度

行2--4的初始化对n个顶点进行，显然是O（n）5--6行O（1）7行n个顶点入队列O（n） 8行--14行，从8行可以看出进行了n遍循环，每遍在第九行调用一次ExtractMin过程，ExtractMin过程需要搜寻邻接表，每一次需要搜寻整个数组，所以一次操作时间是O(n);11行到14行对节点u的邻接表中的边进行检查，总共有|E|次（总共.每条边最多检查一次)，因此是O(E)；合起来就是O（E+n*n） = O（n^2);以上合起来就是O（n）+O（1）+O（n）+O（n^2） == O（n^2).就这样

F. 利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：网络-最短路径算法

G. 怎样用动态规划法求单源最短路径

int[] cost=new int[n];//cost[i]存储i到n-1的子问题的最短路径值
int[] path=new int[n];//path[i]存储状态，使cij+cost[i]最小的j值
//对数组cost[n]和path[n]进行初始化
for(int i=0;i<n-1;i++){
cost[i]=Integer.MAX_VALUE;
path[i]=-1;
}
cost[9]=0;
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>=i;j--){
//得到i的邻接点
if(c[i][j]<Integer.MAX_VALUE&&cost[i]>(c[i][j]+cost[j])){

cost[i]=c[i][j]+cost[j];
path[i]=j;
}
}
}
System.out.println("最短路径为："+cost[0]);
int i=0;
System.out.print("0");
while(i!=n-1){
System.out.print("-->"+path[i]);
i=path[i];

H. 图论中常见的最短路径算法有几种都是什么

主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

I. 请教Dijkstra算法的时间复杂度

我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。相关问题和算法

在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。

OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。

J. Dijkstra算法问题

dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10）=10ms
那么k(40×40）=16[k×（10×10）]=160ms