當前位置:首頁 » 操作系統 » 有向圖的最短路徑演算法

有向圖的最短路徑演算法

發布時間: 2024-05-29 23:25:50

⑴ 求有向圖最短路徑演算法(權重可為負)

單元最短路徑:
1.如果沒有負權環的稀疏圖,可以用SPFA,時間復雜度O(KM)
M是邊數,K是平均入隊列的次數
2.如果沒有負權環的稠密圖,建議用Dijkstra O(N^2),用二叉堆可優化到
O(NlogN),斐波那契堆編程復雜度太高,不易於實現
3.如果有負權環,可以嘗試floyd,O(n^3)

任兩點最短路徑:floyd較好實現,基於重標號johnson也不錯(稀疏圖效率高)
具體程序可以上網查

⑵ 最短路徑問題5種類型

最短路徑問題5種類型有Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法,

擴展知識:

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」,有時被簡稱作「路徑演算法」。最常用的路徑演算法有:
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法,本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題,旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。
演算法具體的形式包括:確定起點的最短路徑問題:即已知起始結點,求最短路徑的問題。
確定終點的最短路徑問題:與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題:即已知起點和終點,求兩結點之間的最短路徑。

⑶ 求有向圖兩個頂點間的最短路徑的方法,用簡單語言或舉例描述。

在交通網路中,常常會提出許多這樣的問題:兩地之間是否有路相通?在有多條通路的情況下,哪一條最近?哪一條花費最少等。交通網路可以用帶權圖表示,圖中頂點表示域鎮,邊表示兩城之間的道路,邊上權值可表示兩城鎮間的距離,交通費用或途中所需的時間等。
以上提出的問題就是帶權圖中求最短路徑的問題,即求兩個頂點間長度最短的路徑。
最短路徑問題的提法很多。在這里僅討論單源最短路徑問題:即已知有向圖(帶權),我們希望找出從某個源點S∈V到G中其餘各頂點的最短路徑。
例如:下圖(有向圖G14),假定以v1為源點,則其它各頂點的最短路徑如下表所示:

圖 G14

從有向圖可看出,頂點v1到v4的路徑有3條:(v1,v2,v4),(v1,v4),(v1,v3,v2,v4 ),其路徑長度分別為:15,20和10。因此v1到v4的最短路徑為(v1,v3,v2,v4 )。
為了敘述方便,我們把路徑上的開始點稱為源點,路徑的最後一個頂點為終點。
那麼,如何求得給定有向圖的單源最短路徑呢?迪傑斯特拉(Dijkstra)提出按路徑長度遞增產生諸頂點的最短路徑演算法,稱之為迪傑斯特拉演算法。
迪傑斯特拉演算法求最短路徑的實現思想是:設有向圖G=(V,E),其中,V={1,2,…,n},cost是表示G的鄰接矩陣,cost[i][j] 表示有向邊<i,j>的權。若不存在有向邊<i,j>,則cost[i][j]的權為無窮大(這里取值為32767)。設S是一個集合,其中的每個元素表示一個頂點,從源點到這些頂點的最短距離已經求出。設頂點v1為源點,集合S的初態只包含頂點v1。數組dist記錄從源點到其他各頂點當前的最短距離,其初值為dist[i]=cost[v1][i],i=2,…,n。從S之外的頂點集合V-S 中選出一個頂點w,使dist[w]的值最小。於是從源點到達w只通過S 中的頂點,把w加入集合S中調整dist中記錄的從源點到V-S中每個頂點v的距離:從原來的dist[v] 和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復上述過程,直到S中包含V中其餘頂點的最短路徑。
最終結果是:S記錄了從源點到該頂點存在最短路徑的頂點集合,數組dist記錄了從源點到 V中其餘各頂點之間的最短路徑,path是最短路徑的路徑數組,其中path[i] 表示從源點到頂點i之間的最短路徑的前驅頂點。

⑷ 求如下有向圖的關鍵路徑以及任意兩點之間的最短距離

用CPM演算法求有向圖的關鍵路徑和用Dijkstra演算法求有向圖的最短路徑的C語言程序如下

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <string.h>

#define MAX 20

#define INF 32767 // 此處修改最大值

#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))

#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))

typedef struct _graph{

char vexs[MAX]; // 頂點集合

int vexnum; // 頂點數

int edgnum; // 邊數

int matrix[MAX][MAX]; // 鄰接矩陣

}Graph, *PGraph;

// 邊的結構體

typedef struct _EdgeData{

char start; // 邊的起點

char end; // 邊的終點

int weight; // 邊的權重

}EData;

//指向節點的位置

int point_node(PGraph g,char c){

for(int i=0;i<g->vexnum;i++){

if(g->vexs[i]==c){

return i;

}

}

return -1;

}

PGraph create_graph(int b[][3],char a[],int n,int e){

char c1,c2; //邊的2個頂點

PGraph g; //矩陣

g=(PGraph)malloc(sizeof(Graph));

//memset()第一個參數 是地址,第二個參數是開辟空間的初始值,第三個參數是開辟空間的大小

memset(g, 0, sizeof(Graph));

printf("頂點個數: ");//頂點數

g->vexnum=n;

printf("%d ",g->vexnum);

printf("邊個數: ");//邊數

g->edgnum=e;

printf("%d ",g->edgnum);

//初始化頂點

for(int j=0;j<g->vexnum;j++){

g->vexs[j]=a[j];

}

for(int i=0;i<g->edgnum;i++){

int p1,p2;

c1=char(b[i][0]);

c2=char(b[i][1]);

p1=point_node(g, c1);

p2=point_node(g, c2);

if (p1==-1 || p2==-1){

printf("input error: invalid edge! ");

free(g);

continue;

}

g->matrix[p1][p2]=b[i][2];

}

for(int i=0;i<g->vexnum;i++){

for(int j=0;j<g->vexnum;j++){

if(g->matrix[i][j]==0)

g->matrix[i][j]=INF;

}

}

return g;

}

//關鍵路徑的最短時間

//關鍵路徑法(Critical Path Method,CPM)

void CPM_road(PGraph g){

int i,j;

int a[MAX]={0},b[MAX]={-10};

int max=0;//最長路徑

for( i=0;i<g->vexnum;i++){//列數遍歷

for( j=0;j<g->vexnum;j++){//行數遍歷

//如果g->matrix[j][i]大於0,說明此頂點有前頂點,由前邊的遍歷可知,前頂點的最長路徑a[j],

//加上g->matrix[j][i]的路徑就是當前a[i]的路徑

if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){

max=g->matrix[j][i]+a[j];

a[i]=max;

}

}

max=0;

}

//顯示最長路徑

printf("第一個頂點到每一個頂點的最長路徑:");

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("V%d ",i+1);

}

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("%d ",a[i]);

}

printf(" ");

printf("最後一個頂點到每個頂點的最長路徑:");

for( i=g->vexnum-1;i>=0;i--){ //列數遍歷

for( j=g->vexnum-1;j>=0;j--){ //行數遍歷

//如果g->matrix[j][i]大於0,說明此頂點有前頂點,由前邊的遍歷可知,前頂點的最長路徑a[j],

//加上g->matrix[j][i]的路徑就是當前a[i]的路徑

if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){

max=g->matrix[i][j]+b[j];

b[i]=max;

}

}

max=0;

}

//顯示最長路徑

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("V%d ",i+1);

}

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("%d ",b[i]);

}

printf(" ");

printf("關鍵路徑: ");

for(i=0;i<g->vexnum;i++){

if(a[i]==a[g->vexnum-1]-b[i]){

printf("V%c ",g->vexs[i]);

}

}

printf(" ");

}

void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){

// 輸出最短距離並列印最短路徑

int i = 0, pre, inverse_path[g->vexnum];

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;

}

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

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

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

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

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

for(i = 0; i < g->vexnum; i++){

distance[i] = g->matrix[start][i]; // 初始化距離數組

if(g->matrix[start][i] < INF){

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

}else{

path[i] = -1;

}

}

used[start] = 1;

path[start] = start;

for(i = 0; i < g->vexnum; i++){

min_dis = INF;

for(j = 0; j < g->vexnum; 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 < g->vexnum; j++){

if(used[j] == 0){

if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){

distance[j] = distance[min_node] + g->matrix[min_node][j];

path[j] = min_node;

}

}

}

}

}

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

return;

}

int main(){

int i,j;

PGraph gp;

char a[]={'1', '2', '3', '4', '5', '6', '7'};

int b[][3]={{'1', '2',3},

{'1', '3',2},

{'1', '4',6},

{'2', '4',2},

{'2', '5',4},

{'3', '4',1},

{'3', '6',3},

{'4', '5',1},

{'5', '7',3},

{'6', '7',4}};

int n=nLENGTH(a);

int e=eLENGTH(b);

gp=create_graph(b,a,n,e);

//列印鄰接矩陣

printf("鄰接矩陣: ");

for (i = 0; i < gp->vexnum; i++){

for (j = 0; j < gp->vexnum; j++)

printf("%d ", gp->matrix[j][i]);

printf(" ");

}

CPM_road(gp);

printf(" ");

for(i=0;i<gp->vexnum;i++){

for(j=0;j<gp->vexnum;j++){

if(i!=j)

shortest_path(gp,i, j);

}

}

return 0;

}


運行結果

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

熱點內容
bat文件復制文件夾 發布:2024-06-13 18:23:10 瀏覽:993
mysql57解壓版 發布:2024-06-13 18:18:48 瀏覽:852
聲樂腳本 發布:2024-06-13 18:18:13 瀏覽:970
dijkstra最短路演算法 發布:2024-06-13 18:17:53 瀏覽:934
c語言如何計算時間 發布:2024-06-13 18:11:36 瀏覽:873
access如何壓縮資料庫 發布:2024-06-13 18:09:55 瀏覽:603
jksjava 發布:2024-06-13 17:40:43 瀏覽:287
小薇千里眼伺服器地址 發布:2024-06-13 17:39:48 瀏覽:949
數據存儲與處理 發布:2024-06-13 17:14:07 瀏覽:731
66php 發布:2024-06-13 17:05:43 瀏覽:162