有向圖最短路徑java

Ⅰ 每一對頂點之間的最短路徑是什麼

每一對頂點之間的最短路徑是指對於給定的帶權有向圖G＝（v，E），要對G中任意一對頂點有序對（vi，vj）（vi≠vj），找出vi到vj的最短距離和vj到vi的最短距離。

解決此問題的一個有效方法是：輪流以每一個頂點為源點，重復執行Dijkstra演算法n次，即可求得有向圖G＝（v，E）中每一對頂點間的最短路徑，總的時間復雜度為0（n2）。

弗洛伊德（Floyd）提出了另一個求任意兩頂點之間最短路徑的演算法，雖然其時間復雜度也是0（n2），但演算法形式更為簡明，易於理解與編程。

1.弗洛伊德演算法的思想弗洛伊德演算法是從圖的鄰接矩陣開始，按照頂點v0，v1，v2，v2，…，vn的次序，分別以每個頂點vk（0≤k＜n）作為新考慮的中間點，在第k－1次運算D（k－1）的基礎上，求出每一對頂點之間vi到vj的最短路徑長度D（k）［i］［j］，計算公式為：

D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝重復執行n次後，D（k）［i］［j］中保留的值就是每對頂點的vi到vj的最短路徑長度。

2.弗洛伊德演算法的步驟（1）從圖的帶權鄰接矩陣G．arcs［］［］開始，即D（－1）＝arcs［］［］，每次以上一次D（k－1）為基礎，用公式D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝計算出D（k）［i］［j］的值，即D（k－1）［i］［k］＋D（k－1）［k］［j］＜D（k－1）［i］［j］才修改，若D（k）［i］［j］修改過，則相應的路徑P（k）［i］［j］也要作相應的修改，即P（k）［i］［j］＝P（k－1）［i］［k］＋P（k－1）［k］［j］。

（2）重復上述過程n次後，D（k）［i］［j］中保存的就是每一對頂點的最短路徑長度，P（k）［i］［j］中保存的就是每一對頂點的最短路徑。

說明：從計算公式可以看出，i＝j是對角線上的元素；i＝k是i行上的元素；j＝k是j列上的元素，這些特殊的頂點不用計算，保留原來的數據值。因此，計算的數據元素減少了很多。

Ⅱ 以鄰接表作存儲結構實現求源點到其餘各頂點的最短路徑的Dijkstra演算法

具體演算法為：

//Dijkstra求單源最短路徑

#include<stdio.h>

#define N 20 //圖的頂點最多數

#define MAX 1000

#define MIN -1

typedef int ElemType;//圖的頂點標識，這里為自然數

//圖的結點結構

typedef struct ArcNode{

ElemType adjvex;//圖的頂點 （該弧指向頂點的位置）

struct ArcNode *nextarc;//指向下一條弧的指針

int info//該弧權值

}ArcNode;

//表頭結點表

typedef struct VertexNode{

ElemType data;

ArcNode *firstarc;

}VertexNode;

//圖

typedef struct AdjList{

VertexNode vertex[N];

int vexnum;//圖的頂點數

int arcnum;//弧數;

int kind;//圖的種類（kind=1為有向圖）

int dist[N];//圖的路徑長度

int path[N];//輔助數組

}AdjList;

//邊

typedef struct{

int i;

int j;

int f;

}Side;

//鄰接表法創建圖

int CreateDAG(AdjList *L){

int i,j;

ArcNode *p=NULL;

//測試用例

Side S[N];

S[0].i=1;S[0].j=3;S[0].f=10;

S[1].i=1;S[1].j=5;S[1].f=30;

S[2].i=1;S[2].j=6;S[2].f=100;

S[3].i=2;S[3].j=3;S[3].f=5;

S[4].i=3;S[4].j=4;S[4].f=50;

S[5].i=4;S[5].j=6;S[5].f=10;

S[6].i=5;S[6].j=6;S[6].f=60;

S[7].i=5;S[7].j=4;S[7].f=20;

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

L->vertex[i].data=i;

L->dist[i]=MAX;//設為最大值，表示不可達

L->path[i]=MIN;//設為最小值，表示尚未初始化

//L->vertex[i].indegree=0;

L->vertex[i].firstarc=NULL;

}

L->kind=1;

L->vexnum=6;

L->arcnum=8;

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

p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=S[i].j;

p->info=S[i].f;

p->nextarc=L->vertex[(S[i].i)].firstarc;

L->vertex[(S[i].i)].firstarc=p;

if(S[i].i==1){//初始頂點為1

L->dist[(S[i].j)]=S[i].f;

//L->path[(S[i].j)]=S[i].f;

}

// L->vertex[(S[i].j)].indegree++;

}

return 1;

}

//輸出鄰接表存儲

void PrintALGraph(AdjList *L){

ArcNode *p=NULL;

int i,k=0;

for(i=1;i<=L->vexnum;i++){

k=L->vertex[i].data;

printf("V%d",k);

// printf(" 入度為%d 鄰接點有 ",(L->vertex[i].indegree));

p=L->vertex[k].firstarc;

while(p!=NULL){

printf(" ->%d",p->adjvex);

p=p->nextarc;

}

printf(" ");

}

}

//Dijkstra求單源最短路徑

void Dijkstra(AdjList *L){

int i=1,j,k=0;

Side s;

L->path[1]=0;

ArcNode *p=NULL;

while(k<10){

s.f=MAX;

for(i=1;i<=L->vexnum;i++){

if(L->path[i]!=MIN){

p=L->vertex[i].firstarc;

if(p!=NULL){

while(p!=NULL){

if(s.f>p->info&&L->path[(p->adjvex)]==MIN){

s.f=p->info;

s.i=i;

s.j=p->adjvex;

}

p=p->nextarc;

}

}

}

}

if(s.f==MAX){

}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){

L->dist[(s.j)]=L->dist[(s.i)]+s.f;

L->path[(s.j)]=L->dist[(s.j)];

}else{

L->path[(s.j)]=L->dist[(s.j)];

}

k++;

}

//輸出

printf("輸出最短路徑: ");

for(i=1;i<=L->vexnum;i++){

if(L->dist[i]==1000||i==1){

printf("v1到v%d不存在最短路徑 ",i);

}else{

printf("v1到v%d的最短路徑是%d ",i,L->dist[i]);

}

printf("path is %d ",L->path[i]);

}

}

int main(){

AdjList *L=(AdjList *)malloc(sizeof(AdjList));

if(CreateDAG(L)==1){

PrintALGraph(L);

Dijkstra(L);

}else{

printf("創建失敗 ");

}

}

(2)有向圖最短路徑java擴展閱讀：

要求帶權有向圖中某一頂點到其他各頂點的最短路徑，常用Dijkstra演算法，該演算法基本思想是，先將圖的頂點分為兩個集合，一個為已求出最短路徑的終點集合（開始為原點v1），另一個為還未求出最短路徑的頂點集合（開始為除v1外的全部結點），然後按最短路徑長度的遞增順序逐個將第二個集合的頂點加到第一組中。

演算法中使用dist數組，dist[i]表示目前已經找到、v1到vi的當前最短路徑，否則為MAX；path數組，作為是否找到該點最短路徑的標志，path[i]==MIN表示為未找到，否則為最短路徑值。