Ⅰ 圖論：最短路演算法有哪些以及它們的比較
弗洛伊德 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.找到一條路徑，和當前長度一樣，但限制值比當前小
任意一條就更新最短路，輸出最後的結果就可以了...