有向圖的最短路徑演算法
⑴ 求有向圖最短路徑演算法（權重可為負）
單元最短路徑：
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.