dijkstra演算法做題

A. 用Dijkstra演算法求圖中從頂點a到其他各頂點間的最短路徑，並寫出執行演算法過程中各步的狀態。

迪克斯加（Dijkstra）演算法(最短路徑演算法)是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中任意兩個頂點之間的最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
迪科斯徹演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0）， 同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到v的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到u的路徑。這條路徑的長度是d+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d達到它最終的值的時候每條邊(u,v)都只被拓展一次。
演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找權值最小的點為node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各點的權值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.

B. 解釋一下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就和你的這本書中獲得永久標號是相似的)

C. 離散數學迪克斯特拉演算法解題詳細過程

18·解：題中E、F分別在AA1、C1B1上，所以「展開」後的圖形中必須有AA1、C1B1；故「展開」方式有以下四種：
（ⅰ）沿CC1將面ACC1A1和面BCC1B1展開至同一平面，如圖1，求得：EF2=；
（ⅱ）沿BB1將面ABB1A1和面BCC1B1展開至同一平面，如圖2，求得：EF2=；
（ⅲ）沿A1B1將面ABB1A1和面A1B1C1展開至同一平面，如圖3，求得：EF2=；
（ⅳ）沿A1C1將面ACC1A1和面A1C1B1展開至同一平面，如圖4，求得：EF2=；
比較可得（ⅳ）情況下，EF的值最小；
故EF的最小值為．

D. 利用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）。

以上內容參考：網路-最短路徑演算法

E. dijkstra演算法是什麼

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。

對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

堆優化

思考

該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。

實現

1、將源點加入堆，並調整堆。

2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。

3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點

1):若該點在堆里，更新距離，並調整該元素在堆中的位置。

2):若該點不在堆里，加入堆，更新堆。

4、若取到的u為終點，結束演算法；否則重復步驟2、3。

F. 利用Dijkstra演算法,求下圖從1出發到其餘各點的最短路徑.

MVC方法常用於構建用戶界面在Smalltalk。通過MVC設計模式隱藏在可以幫助你了解我們所說的「模範」的意思。

MVC包括三種類型的對象，模型是應用程序對象，查看其屏幕表示，控制器定義了處理用戶輸入（響應）模式。在MVC方式之前，應用程序，通常是三個對象組合在一起，這些功能結合在一起，將它們分開MVC應用程序，旨在提供靈活性和可重用性。

MVC通過創建訂閱/通知視圖和模型，視圖和模型對象之間的分離協議。視圖對象必須確保它反映了狀態模型表示對象，當數據模型對象的變化，模型對象的通知（通知）視圖對象，作為反應，這種行為，每有一個視圖對象進行更新的機會。這種方法使得有可能對多個視圖的對象模型中的對象提供不同的表示形式。您還可以創建一個新的視圖對象模型對象，而不是重新寫模式。下圖顯示了一個模型和三視圖：點擊看詳細從表面上看，這個例子反映的視圖和模型設計的分離。然而，這是專為一類的更一般的問題：降低了蓮和性的目的，這樣，當一個對象改變時，也不會影響到其它的目的，甚至不需要知道另一個對象的實現細節。這更普遍的模式將在Observer模式描述。另一個特點是方式

MVC，視圖對象是可嵌套定義。例如，通過嵌套對象視圖對象按鈕控制面板按鈕視圖包含復雜的實施;對象觀眾嵌套的用戶界面視圖的對象可以被重新使用的調試器組件。使用CompositeView類（查看子類），以支持嵌套圖，其行為和查看對象，可用於任何場合視圖對象可以使用的行為一致MVC方法。

因此，我們可以把復合視圖這樣的一種方式來解決它的設計（時尚）的一個組成部分。同樣，這樣的設計可以抽象另一個更普遍的問題（解決方案）：在某些情況下，我們進入的對象群體，並視為一組處理單個對象。通過這種方式，我們用它來形容復合設計模式。它可以讓你建立一流的水平，在這個水平上，某些子類定義基本對象（如按鈕），而其他類可以定義合成對象（CompositeView），合成對象可以組裝成更復雜的對象原始對象。

同樣，MVC也可以改變視圖類（視圖）的方式，用戶的反應，不改變其視覺表現。你可能想改變其響應於鍵盤，如使用彈出菜單，而不是命令鍵的方式。 MVC封裝的響應機制，該對象（控制器）的控制。控制器具有一個類層次結構，並且容易從現有的控制器來實現建立一個變種 - 一個新的控制器。

視圖（View），通過對象（實例）控制器對象的實例，以實現特定的應對策略。為了實現不同的政策，可以簡單地使用不同的控制器實例來替換當前實例。即使在運行時改變控制器的視圖來改變響應於用戶輸入（策略）的對象圖。例如，一個瀏覽對象可以被設置為關閉狀態，即，在沒有任何用戶輸入的響應。為了實現這一目標，就乾脆讓控制器忽略所有輸入事件。這

視圖 - 控制器關系，這是策略設計模式的一個典型例子。所謂策略，這樣一種對象，它表示的演算法。當你要替換演算法（無論是靜態還是動態替換替換），這是特別有用，這樣的演算法可能有很多變數，或有復雜的數據結構。

MVC中也使用其他的設計模式，例如，使用工廠方法模式來描述默認控制器類圖;使用裝飾圖案添加滾動條，以查看等。但在MVC的方式主要是上述觀察，綜合和戰略設計模式。

G. 用dijkstra演算法計算源點到個結點的最短路徑....謝謝親愛的朋友~ 詳細答案

(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)
1． 置集合S={2,3,...n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊) 2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3
3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2

H. 提供幾道Dijkstra演算法的ACM水題練習

浙江大學ZOJ上的1221題可以算是最最基礎的Dijkstra演算法練習。。

由於Dijkstra 與 prim 有驚人的相似之處，所以這道題要好好體會。。

希望對你有所幫助！！！！！

本人相當建議初學者做做。。下面是本人的AC代碼：

#include<iostream>
#include<algorithm>
using namespace std;

int map[21][21];
int flag[21];
int length[21];
int dijkstra(int from,int to)
//Dijkstra演算法真的跟Prim很像。。要好好體會體會。。
{
int q,w,m;
memset(flag,0,sizeof(flag));
memset(length,0,sizeof(length));
for(q=1;q<=20;q++)
length[q]=map[from][q];
flag[from]=1;
length[from]=0;
for(q=1;q<20;q++)
{
int min=9999,y;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&min>=length[w])

min=length[w],y=w;
}
flag[y]=1;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&map[y][w]==1&&length[w]>length[y]+1)

length[w]=length[y]+1;
}
}
return length[to];
}
int main()

//這是比較簡單的求無向圖無權任意兩點的最短距離
{
int t,q,w,m,count=1;
while(scanf("%d",&t)!=EOF)
//一開始這里我寫為：while(1)。。本來是想讓他不停輸入的。。誰知道TLE了。。
{
for(q=1;q<=20;q++)
for(w=1;w<=20;w++)

map[q][w]=1000;
while(t--)
{
scanf("%d",&w);
map[1][w]=map[w][1]=1;
}
for(q=2;q<20;q++)
{
scanf("%d",&t);
while(t--)
{

scanf("%d",&w);

map[q][w]=map[w][q]=1;
}
}
scanf("%d",&w);
//cout<<"Test Set #"<<count<<endl;
printf("Test Set #%d\
",count);
count++;
int from,to;
while(w--)
{

scanf("%d %d",&from,&to);
//cout<<from<<" to "<<to<<":"<<dijkstra(from,to)<<endl;
printf("%d to %d: %d\
",from,to,dijkstra(from,to));
}
printf("\
");
}
return 0;
}

I. Dijkstra演算法問題

dijkstra演算法的時間復雜度是O(n²),
不妨設為kn²,其中次數小於1的項忽略
k(10×10）=10ms
那麼k(40×40）=16[k×（10×10）]=160ms