dijkstra演算法求最短路徑

❶ 數據結構中迪傑斯特拉演算法求最短路徑

dijkstra演算法本身求的是一點到其他所有點的最短距離，而不是具體的路徑，因此還需要一個額外的數組來記錄推導最短距離的過程中經過的每一個結點，這樣才能求出這個最短距離的具體路徑。

❷ 用dijkstra演算法求a到f的最短路徑

#include<stdio.h>
inta[205][205];//記錄鄰接矩陣
intdist[205];//到每個點的最短路
intm,n;//m條路，n個點
constintINF=0xfffffff;
voidinit()//初始化數據
{
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
a[i][j]=(i==j?0:INF);
}

voiddijkstra(intu)//從第u個點開始走
{
intsign[205]={0};//標記走過否
intx=u;
inti,j;
for(i=0;i<n;i++)//初始化到各點距離
dist[i]=a[x][i];
dist[x]=0;//到本身距離為0
sign[x]=1;//改點以走過
for(i=1;i<=n-2;i++)
{
intmin=INF;
for(j=0;j<n;j++)//在為走過的點中取距離x最短的點
{
if(!sign[j]&&min>dist[j])
{
min=dist[j];
x=j;
}
}
sign[x]=1;//標記，已走過

for(j=0;j<n;j++)//x以改變，更新dist[]值
{
if(!sign[j]&&dist[x]+a[x][j]<dist[j]&&a[x][j]<INF)
dist[j]=a[x][j]+dist[x];
}
}
}
intmain()
{
inti;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
intx,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z<a[x][y])//取兩點多條路最小路
a[x][y]=z;
if(z<a[y][x])
a[y][x]=z;
}
ints,t;
scanf("%d%d",&s,&t);
dijkstra(s);

if(dist[t]<2000000)
printf("%d
",dist[t]);
else
printf("-1
");
}
return0;
}

參考鏈接 ：http://blog.csdn.net/ouyangying123/article/details/38706957

❸ 求出最短路徑，要過程，用Dijkstra演算法。。。

從v1開始遍歷
v2 = 2;
v3 = 5;
v2較小所以跳到v2
v3 = 4;

v4 = 6;
v5 = 8;
v3較小所以跳到v3
v4 = 5;
v6 = 7;
v4較小所以跳到v4
v6 = 6;
v7 = 9;
v6較小所以跳到v6
v7 = 8;

所以最後結果v1 -> v7最短路徑為v1->v2->v3->v4->v6->v7,最短路徑長度為8

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

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

❺ 數據結構 dijkstra演算法 最短路徑

你這個演算法到這步，還沒結束。
因為S=【1,2,4】，U=【3】。下面應該把【3】，加入到S中。進行路徑的判斷。
3加入進來，發現1-》2-》4大於1-》3-》4。所以1-》4的距離會重新算。

❻ 以鄰接表作存儲結構實現求源點到其餘各頂點的最短路徑的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("創建失敗 ");

}

}

(6)dijkstra演算法求最短路徑擴展閱讀：

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

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

❼ 用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

❽ 單源最短路徑的Dijkstra演算法

將圖G中所有的頂點V分成兩個頂點集合S和T。以v為源點已經確定了最短路徑的終點並入S集合中，S初始時只含頂點v,T則是尚未確定到源點v最短路徑的頂點集合。然後每次從T集合中選擇S集合點中到T路徑最短的那個點，並加入到集合S中，並把這個點從集合T刪除。直到T集合為空為止。
具體步驟
1、選一頂點v為源點，並視從源點v出發的所有邊為到各頂點的最短路徑（確定數據結構：因為求的是最短路徑，所以①就要用一個記錄從源點v到其它各頂點的路徑長度數組dist[],開始時，dist是源點v到頂點i的直接邊長度，即dist中記錄的是鄰接陣的第v行。②設一個用來記錄從源點到其它頂點的路徑數組path[],path中存放路徑上第i個頂點的前驅頂點）。
2、在上述的最短路徑dist[]中選一條最短的，並將其終點（即<v,k>）k加入到集合s中。
3、調整T中各頂點到源點v的最短路徑。 因為當頂點k加入到集合s中後，源點v到T中剩餘的其它頂點j就又增加了經過頂點k到達j的路徑,這條路徑可能要比源點v到j原來的最短的還要短。調整方法是比較dist[k]+g[k,j]與dist[j]，取其中的較小者。
4、再選出一個到源點v路徑長度最小的頂點k,從T中刪去後加入S中，再回去到第三步，如此重復，直到集合S中的包含圖G的所有頂點。 SPFA實際上是Bellman-Ford基礎上的隊列優化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每條邊(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

❾ 利用Dijkstra演算法求有向網圖的最短路徑

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為最短路徑