Ⅰ 图论：最短路算法有哪些以及它们的比较
弗洛伊德 n^3 的时间把n个点两两的最短路求出来
迪杰斯特拉 n^2的时间(用堆优化到Nlog(M),M是边数)，单源最短路，但是不能对付有负权的图
SPFA，M*k的时间（K是一个常数），单源最短路，能对付有负权的图
感觉常用的就这三个了吧。。
Ⅱ 用图论做一个求迷宫最短路径的算法
01.#include <stdio.h>
02.#define MAXN 10
03.int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
04.char name[] = {'U', 'D', 'L', 'R'};
05.int q[MAXN * MAXN]; //队列，保存当前结点编号
06.int vis[MAXN][MAXN], nMap[MAXN][MAXN];
07.int m, n; //行、列数
08.int dir[MAXN * MAXN];
09.int fa[MAXN][MAXN], dis[MAXN][MAXN], last_dir[MAXN][MAXN];
10.void funcInit();
11.void bfs(int x, int y);
12.void funcInput();
13.void print_path(int x, int y);
14.int main()
15.{
16. funcInput();
17. funcInit();
18. bfs(0, 0);
19. print_path(m - 1, n - 1);
20. return 0;
21.}
22.void funcInit()
23.{
24. int i, j;
25. for (i = 0; i != m; ++i)
26. {
27. for (j = 0; j != n; ++j)
28. {
29. vis[i][j] = 0;
30. dis[i][j] = 0;
31. }
32. }
33.}
34.void funcInput()
35.{
36. int i, j;
37. scanf("%d %d", &m, &n);
38. for (i = 0; i != m; ++i)
39. {
40. for (j = 0; j != n; ++j)
41. {
42. scanf("%d", &nMap[i][j]);
43. }
44. }
45.}
46.void bfs(int x, int y)
47.{
48. int front = 0, rear = 0;
49. int d, u; //方向标记、结点编号
50.
51. u = x * m + y;
52. vis[x][y] = 1;
53. fa[x][y] = u;
54. q[rear++] = u; //将当前结点编好放入队列
55.
56. while (front != rear)
57. {
58. u = q[front++];
59. x = u / m; y = u % m;
60. for (d = 0; d != 4; ++d)
61. {
62. int nx = x + dx[d], ny = y + dy[d];
63. if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && !nMap[nx][ny])
64. {
65. int v = nx * m + ny;
66. q[rear++] = v;
67. vis[nx][ny] = 1;
68. fa[nx][ny] = u;
69. dis[nx][ny] = dis[x][y] + 1; //记录路径长度
70. last_dir[nx][ny] = d; //记录移动方向标记
71. }
72. }
73. }
74.}
75.void print_path(int x, int y)
76.{
77. int c = 0;
78.
79. while (1)
80. {
81. int fx = fa[x][y] / m;
82. int fy = fa[x][y] % m;
83. if (fx == x && fy == y) break;
84. dir[c++] = last_dir[x][y];
85. x = fx; y = fy;
86. }
87. while (c--)
88. {
89. putchar(name[dir[c]]);
90. putchar('/n');
91. }
92. printf("最短路径长度为:%d/n", dis[m-1][n-1]);
93.}
Ⅲ 图论中常见的最短路径算法有几种都是什么
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
Ⅳ 这是一个图论的问题
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等
注意：你的指定点开始的问题，直接从把下面的东西看完后，应用（6）就可以解决，任意开始点的话，就把所有点都指定一下就行了。。。
再补充一个，这个算法一般图论书上都有，但是写的非常之高深莫测，看不懂的。。。建议去看清华大学的数据结构与算法这本书上的算法，（蓝色封皮的）
设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
①初始化
初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。
②重复以下工作，按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
注意：
①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1，红点2，…，红点n，蓝点k
距离为：源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。
若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]=SD(k)。
初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。
注意：
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
（4）k扩充红点集s后，蓝点集估计距离的修改
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。
对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。
所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。
（5）Dijkstra算法
Dijkstra(G，D，s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s}；D[s]=0； //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]； //设置i初始的估计距离为w<s，i>
//以下是扩充红点集
for(i=0;i<n-1;i++)do{//最多扩充n-1个蓝点到红点集
D[k]=min{D[i]：all i V-S}； //在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞)
return； //蓝点集中所有蓝点的估计距离均为∞时，
//表示这些顶点的最短路径不存在。
S=S∪{k}； //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时，用新路径的长度修改D[j]，
//使j离s更近。
D[j]=D[k]+G[k][j]；
}
}
（6）保存最短路径的Dijkstra算法
设置记录顶点双亲的向量P[0．．n-1]保存最短路径：
当顶点i无双亲时，令P[i]=-1。
当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。
。
Dijkstra算法的时间复杂度为O(n2)
参考资料：http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.2.htm
Ⅳ 图论最短路
var
a,f :array[1..80,0..80] of real;
b :array[1..80,0..80] of boolean;
minj,mini,i,j,m,n,k :longint;
sum,temp,min :real;
begin
readln(n,m);
for i :=1 to n do
for j :=1 to n do
read(a[i,j]);
readln;
for i :=1 to n do
for j :=0 to m do
f[i,j] :=maxlongint;
f[1,0] :=0;
fillchar(b,sizeof(b),true);
repeat
min :=maxlongint;
for i :=1 to n do
for j :=0 to m do
if (b[i,j])and(f[i,j]<min)then
begin
min :=f[i,j];
mini :=i;
minj :=j;
end;
if min=maxlongint then break;
if (mini=n)and(minj=m) then break;
b[mini,minj] :=false;
for i :=1 to n do
if a[mini,i]<>0 then
begin
temp :=a[mini,i];
for j :=minj to m do
begin
if (b[i,j])and(f[mini,minj]+temp<f[i,j])then
f[i,j] :=f[mini,minj]+temp;
temp :=temp/2;
end;
end;
until false;
writeln(f[n,m]:0:2);
end.
Ⅵ 已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路
初始化d[i]为无穷大，由于从v4开始，所以将d4=0，标记v4已选择。
下面开始Dijkstra算法：
和v4相连的且未标记的点有v2和v6，这样更新d2=20，d6=15，选择未标记所有点中最小的d6=15，标记v6已选择，这样我们算出了v4->v6最短距离d6=15；
从v6开始，和v6相连的且未标记的是v2，此时算d6+6=21>20,所以不更新d2，选择未标记所有点中最小的d2=20，标记v2已选择，这样算出了v4->v2最短距离d2=20；
从v2开始，和v2相连的且未标记的有v1和v5，d1=d2+10=30,d5=d2+30=50，选择未标记所有点中最小的d1=30，标记v1已选择，这样我们算出了v4->v1最短距离d1=30；
从v1开始，和v1相连的且未标记的有v3，d3=d1+15=45，选择剩下没被选的所有点的最小的d3=45(d5=50)，标记v3已选择，这样我们算出了v4->v3最短距离d3=45
从v3开始，没有出去的路径，不更新距离，选择剩下没被选的所有点的最小的d5=50，标记v5已选择，这样我们算出了v4->v5最短距离d5=50.
此时所有的点都被访问，结束。
注：上面的标记点已选择注意下，在算法的实现中用的是将所有的点放入队列中，一旦一个点被选择就是说求出了最短距离，就从此队列删除该点，一直到此队列为空，结束算法，我写标记只是为了方便理解。
希望能帮你清晰了解Dijkstra算法，图论中很重要的算法之一。
Ⅶ 求解：图论中常见的最短路径算法有几种都是什么
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
Ⅷ 求图论例题 最小生成树,拓扑,最短路等等的例题,其他图论题也行,联赛提高组就行了.
《离散数学》补充练习题（2011.05.30）
1、将下列命题符号化.
（1）小李边读书边听音乐.
（2）现在没下雨,可也没出太阳,是阴天.
2、证明等价关系： .
3、概述求解主合取范式的主要方法和步骤,并求公式 的主合取范式.
4、将下列论证用命题符号表示,然后求证逻辑推论是否成立.
如果天热则蝉鸣叫,如果蝉鸣叫则小王不睡觉,小王游泳或睡觉,所以如果天热则小王游泳.
5、将下列语句用谓词公式表示.
（1）不劳动者不得食.
（2）每个人的祖父都是他父亲的父亲.
6、给定集合 , 均是 上的二元关系, , .
（1）画出 的关系图；
（2）写出 的关系矩阵；
（3）写出 所具有的性质；
（4）求 .
7、设 是集合 上的二元关系.证明 .
8、简述传递闭包的定义,并求 上关系 的传递闭包.
9、列出色数 为的三个图： .
10、 阶完全图的色数为： .
11、 阶树的色多项式为： .
12、 阶完全图的色接多项式为： .
13、如下图所示的图的邻接矩阵为,关联矩阵为.
14、设 阶图的各顶点的度分别为 ,则称 为该图的度序列.度序列为 的简单图是.
15、是否存在度序列为 , 的简单图?若存在,给出一个图；若不存在,请说明理由.
16、画出如下图的所有生成子图.
17、设图 如下图所示,求该图的生成树个数 .
18、已知图G（V、E）,画出G－V5,G－v3v4,G[{v2,v3,v5}],G[{v3v4,v4,v6,v7v8}]
G：
19、已知图G的邻接矩阵 ,画出G,并求出度序列.
20、证明：偶图G的任意子图H仍为偶图.
21、证明：设图G（V、E）的度序列为（ ）,边数为q,则
22、证明：整数序列（6,6,5,4,3,3,1）不可能为一个简单图的图序列.
23、证明顶点度数均为 的简单连通图是圈.
23、若图G是 不连通的,则其补图GC是连通的.
24、证明：设 是由 和 两个连通分支组成的图,则其色多项式 .
25、证明：设 是由 和 两个连通分支组成的图,则其色数 .
26、设图G（V、E）且|V|＝p,|E|＝q,则G为树当且仅当G为连通的且p＝q＋1.
27、证明：图G为树当且仅当G的任意两个不同顶点之间存在唯一的一条路.
28、画出全部非同构的6阶树.
29、利用Cayley公式计算图G的生成树数目（写出演算过程）.
G：
30、下列图是否为Enler图?
G1： G2：
31、证明：设 为 条边的 阶连通简单图且 ,则 包含圈.
32、证明：非平凡树的最长路的起点和终点均为悬挂点.
33、证明：恰好有两个悬挂点的树是一条路.
34、证明：图G为非平面图.
G：
35、给出下图G的一个最大匹配（最大对集）.
G：
36、设图G有完美匹配,则G为偶数阶图.
37、证明：路至多有一个完美匹配.
38、写出p（≥1）阶树T的色多项式,并确定T的色数.
39、写出5个阶轮图W5的色多项式,并求χ（w5）
W5：
40、设G为任一偶图,则χ（G）≤2.
41、证明：非平凡连通偶图 的色数为 .
42、证明圈 的色数为 或 .
43、证明：设 为具有 条边的 阶极大平面图,则 .
44.证明：在空间中,不可能有这样的多面体存在,它们有奇数个面,而它们的每个面又都有奇数条边.
证明：假设存在这样的多面体,将这多面体的面用顶点表示,当且仅当两个面有公共棱时,在相应的顶点间连一边,得图G.按题意,G有奇数个奇顶点.显然,这样的图不存在,故这样的多面体是不存在的.
45. A wolf, a goat and a cabbage are on one bank of a river. A ferryman wants to take them across, but since his boat is small, he can take only one of them at a time. For obvious reasons, neither the wolf and the goat nor the goat and the cabbage can be left unguarded. How is the ferryman going to get them across the river?
在一河岸有狼、羊和卷心菜,农夫要将它们渡过河去,但由于他的船太小,每次只能载一样葡萄东西,并且,狼和羊,羊和卷心菜都不能在无人照看的情况下留在一起.问农夫有无办法将它们渡过河去?若有,给出其实施办法.
人、狼、羊、菜四种东西的任意组合,共有24=16种情况,其中狼羊菜、羊菜、狼羊三种情况不允许,因而这三种情况的余：人、人狼、人菜三种情况也不会出现.这样,岸上只能有如下10种情况：
人狼羊菜、 人狼羊、 人狼菜、 人羊菜、 人羊、
空、 菜、 羊、 狼、 狼菜.
将这10种状态各用一个点表示,且两种状态的两个点有边相连当且仅当该两种状态可用载人（或加一物）的渡船互相转换.于是可得下图：
我们的问题就转化为求一条从“人狼羊菜”到“空”的路.从而可求得渡河办法.
Ⅸ 帮忙讲一下最短路算法的过程，比如在一个图上怎么求出最短路，举个例子。
比如有一直线CD，CD是河，CD上边有AB两个点，分别到河边不同距离，现在要去河边打水，问从哪去打水距离最近？
从A出发的话以河为中间分界线，镜像A'到对面，然后A'－B连线，A'B直线跟CD交界点打水就是最近距离，如果由B出发的话原理一样，也可以镜像出B'连成AB'画出一交界点也是最近的打水点，
Ⅹ 图论问题-有限制的最短路-noip
其实这三个都一样，都可以这样来处理：
由于有另一限制，，我们用另一个数组c[i,j]来存，i到j当前最短路径的限制值
满足：1.找到一条路径，比当前短。
2.找到一条路径，和当前长度一样，但限制值比当前小
任意一条就更新最短路，输出最后的结果就可以了...