dijkstra算法

‘壹’ dijkstra算法复杂度是多少

1、简单复杂度是O(n2)。

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

1functionDijkstra(G,w,s)
2foreachvertexvinV[G]
3d[v]:=infinity
4previous[v]:=undefined
5d[s]:=0
6S:=emptyset
7Q:=setofallvertices
8whileQisnotanemptyset
9u:=Extract_Min(Q)
10S:=Sunion{u}
11foreachedge(u,v)outgoingfromu
12ifd[v]>d[u]+w(u,v)
13d[v]:=d[u]+w(u,v)
14previous[v]:=u

O（n）+O（1）+O（n）+O（n^2） == O（n^2).

2、用堆优化后的时间复杂度：O((m+n)log n)

‘贰’ 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*算法，以减小最短路径的搜索范围。

‘叁’ Prim算法和Dijkstra算法的异同

所谓距离矢量即是将一条路由信息考虑成一个由目标和距离（用 Metric 来度量）组称的矢量，每一台路由器从其邻居处获得路由信息，并在每一条路由信息上叠加从自己到这个邻居的距离矢量，从而形成自己的路由信息。 在一个链路状态路由选择中，一个结点检查所有直接链路的状态，并将所得的状态信息发送给网上所有的其他的结点，而不仅仅是发给那些直接相连的结点。每个节点都用这种方式，所有其他的结点从网上接收包含直接链路状态的路由信息。 每当链路状态报报文到达时，路由结点便使用这些状态信息去更新自己的网路拓扑和状态“视野图”，一旦链路状态发生改变，结点对跟新的网络图利用Dijkstra最短路径算法重新计算路由，从单一的报源发出计算到达所有的结点的最短路径。 看明白了么？ 最简单理解。。距离矢量算法是静态的。。。链路状态路由算法是动态的，，随时改变的。。 距离矢量算法，一旦相邻节点发生故障，传输就出终止； 链路状态路由算法，一旦相邻的一个节点发生故障，会自动转移数据包到另外的节点进行传输过程。

‘肆’ Dijkstra算法问题

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

‘伍’ dijkstra算法

楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CB<AB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FB<AB;等等诸如此类的情况。
简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。
而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。
当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^

‘陆’ Dijkstra算法

这是我自己写的一个简单的DIJKSTRA算法，其中测试数据是
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
结构清晰简单，对于你要搞懂这个算法很有帮助。有不懂的可以问我：我的QQ是396730783
#include"stdio.h"
#define MAX 100000000
int main()
{
int map[101][101];
int dis[101];
int a,b,c;
int i,j,k,n,m;
int min;
while(scanf("%d",&n)==1)
{
int final[101] = {0};
scanf("%d",&m);
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
map[i][j] = map[j][i] = MAX;
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = c;
}
for(i=1;i<n;i++)
{
dis[i] = map[0][i];
}
dis[0] = 0;
final[0] = 1;
for(i=0;i<n-1;i++)
{
min = MAX;
for(j=1;j<n;j++)
{
if(!final[j] && min > dis[j])
{
min = dis[j];
k = j;
}
}
final[k]=1;
for(j=1;j<n;j++)
{
if(!final[j] && dis[k]+map[k][j]<dis[j])
dis[j] = dis[k]+map[k][j];
}
}
for(i=1;i<n;i++)
{
if(dis[i] == MAX)
printf("不可通");
else
printf("%5d",dis[i]);
}
printf("\n");

}
return 0;

}

‘柒’ folyd与dijkstra算法比较

floyd是所有顶点间距离、dijkstra是单顶点到别的所有顶点距离
floyd算法权值可以小于0，dijkstra算法权值不得小于0
floyd算法是动态规划、dijkstra是贪心法
floyd是O(n^3)，dijkstra算法是 O(n^2)

‘捌’ 比较Dijkstra算法与Floyd算法。

（1）Dijkstra算法：在网络中用得多，一个一个节点添加，加一个点刷一次路由表。

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

（2）Floyd算法：把所有已经连接的路径都标出来，再通过不等式比较来更改路径。

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

‘玖’ dijkstra算法是什么

迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。

算法把一个图（G）中的点划分成了若干部分：

1）：原点（v）；

2）：所有周边点（C）；

另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。

这样就可以进一步划分图（G）：

1）：原点（v）；

2）：已求出v至其最短路径的周边点（S）；

3）：尚未求出v至其最短路径的周边点（Other=C-S）；

算法的主体思想：

A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；

B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；

C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。

重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——

‘拾’ 解释一下dijkstra算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过C语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。
Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。

t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现

t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。
这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);
对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);
对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);
v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
t=6: 同理

啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(网络)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)