用d演算法求v1到其他各點的距離

1. 用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.

2. 從某個源點到其餘各頂點的最短路徑

要代碼?? 怎麼還熟練使用C++可視環境.
代碼就不發了,數據結構的書上寫的很詳細 改改就能用了.
DLL 函數 __declspec(dllexport) 加到函數前面就成導出的了,
可以用LordPE 查看導出表查看其他DLL的導出函數
調試方法 看看手冊 F5調試執行,F7單步F8步過F9斷點,其餘自己摸索下
在工程調試裡面可以設置Memory,Stack,Watch,Auto,自己觀察下就會了

3. 數據結構求最短路徑

用Dijkstra演算法求從V1頂點到其他各頂點的最短距離和最短路徑的C語言程序如下

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define N 6 // 頂點數

#define INF 32767

int adj_arr[N][N] = {{INF, 2, 3, INF, INF, INF},

{INF, INF, INF, 5, INF, INF},

{INF, INF, INF, 3, 10, INF},

{INF, INF, INF, INF, INF, 4},

{INF, INF, INF, INF, INF, INF},

{INF, INF, INF, INF, 2, INF}}; // 用一個全局二維數組存儲帶權有向圖的鄰接矩陣

void shortest_path(int start, int end);

void print_shortest_path(int* distance,int* path,int* used,int start,int end);

int main(){

int i;

char s1[3];

for(i=1;i<6;i++){

shortest_path(0, i);

}

return 0;

}

void shortest_path(int start, int end){ // 基於Dijkstra演算法的最短路徑函數

int distance[N]; // 用於存放起始點到其餘各點的最短距離

int path[N]; // 用於存放起始點到其餘各點最短路徑的前一個頂點

int used[N] = { 0 }; // 用於標記該頂點是否已經找到最短路徑

int i, j, min_node, min_dis, pass_flag = 0;

for(i = 0; i < N; i++){

distance[i] = adj_arr[start][i]; // 初始化距離數組

if(adj_arr[start][i] < INF){

path[i] = start; // 初始化路徑數組

}else{

path[i] = -1;

}

}

used[start] = 1;

path[start] = start;

for(i = 0; i < N; i++){

min_dis = INF;

for(j = 0; j < N; j++){

if(used[j] == 0 && distance[j] < min_dis){

min_node = j;

min_dis = distance[j];

pass_flag++; // 標記是否存在通路

}

}

if(pass_flag != 0){

used[min_node] = 1;

for(j = 0; j < N; j++){

if(used[j] == 0){

if(adj_arr[min_node][j] < INF && distance[min_node] + adj_arr[min_node][j] < distance[j]){

distance[j] = distance[min_node] + adj_arr[min_node][j];

path[j] = min_node;

}

}

}

}else{

printf("沒有通路! ");

return;

}

}

print_shortest_path(distance, path, used, start, end);

return;

}

void print_shortest_path(int* distance,int* path,int* used,int start,int end){ // 輸出最短距離並列印最短路徑

int i = 0, pre, inverse_path[N];

char s1[3],s2[3];

sprintf(s1, "V%d", (start+1));

sprintf(s2, "V%d", (end+1));

printf("從%s頂點到%s頂點的最短距離: %d ", s1, s2, distance[end]);

inverse_path[i] = end;

pre = path[end];

if(pre == -1){

printf("沒有通路! ");

}else{

while(pre != start){

inverse_path[++i] = pre;

pre = path[pre];

}

inverse_path[++i] = start;

printf("從%s頂點到%s頂點的最短路徑: ", s1, s2);

for(; i > 0; i--){

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s -> ", s1);

}

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s ", s1);

}

return;

}

4. 已經圖G的邊權矩陣D[1],D[2],D[3]、、、D[n]，已經Vi到Vj的最短距離是c，找出Vi到Vj的中間過程。

演算法過程把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。
定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。 把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。
在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。 比如，要尋找從V5到V1的路徑。
根據D，假如 D(5,1)=3，D(3,1)=2，D(2,1)=1則說明從V5到V1經過V3，從V3到V1經過V2，V2到V1直接相連，路徑為 {V5,V3,V2,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連

5. 迪傑克斯拉演算法怎麼也不明白

當然不一樣啦，迪傑克斯拉演算法，求的是單點到其他頂點最短的路徑長度，而PRIM演算法求的最小代價生成樹

6. 用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

7. 求程序 在matlab上用Dijkstra和Floyd演算法求出v1到v8的最短路徑。。

function[distance,path]=Dijkstra(W,st,e)
n=length(W);
D=W(st,:);
visit=ones(1:n);
visit(st)=0;
parent=zeros(1,n);
path=[];

fori=1:n-1
temp=[];
forj=1:n
ifvisit(j)
temp=[tempD(j)];
else
temp=[tempinf];
end
end
[~,index]=min(temp);
visit(index)=0;

fork=1:n
ifD(k)>D(index)+W(index,k)
D(k)=D(index)+W(index,k);
parent(k)=index;
end
end
end

distance=D(e);
t=e;
whilet~=st&&t>0
path=[t,path];
p=parent(t);t=p;
end
path=[st,path];%最短路徑
end

W=[0310InfInfInfInfInf;
30Inf5InfInfInfInf;
10Inf06InfInfInfInf;
Inf5604InfInfInf;
InfInfInf4095Inf;
InfInfInfInf9034;
InfInfInf105306;
InfInfInfInfInf460];
[distance,path]=Dijkstra(W,1,8);


>>distance
distance=
23
>>path
path=
124578

8. 已知帶權有向圖如圖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演算法，圖論中很重要的演算法之一。

9. 試用Dijkstra演算法求從v1到其餘各頂點的最短路徑，寫出每一步的狀態。求大神解答。演算法我會，主