單源最短路徑dijkstra演算法

❶ 最短路徑的Dijkstra演算法

Dijkstra演算法（迪傑斯特拉）是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。可以用堆優化。
Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。
其採用的是貪心法的演算法策略
大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復第2和第3步,直到OPEN表為空，或找到目標點。 #include<iostream>#include<vector>usingnamespacestd;voiddijkstra(constint&beg,//出發點constvector<vector<int>>&adjmap,//鄰接矩陣，通過傳引用避免拷貝vector<int>&dist,//出發點到各點的最短路徑長度vector<int>&path)//路徑上到達該點的前一個點//負邊被認作不聯通//福利：這個函數沒有用任何全局量，可以直接復制！{constint&NODE=adjmap.size();//用鄰接矩陣的大小傳遞頂點個數，減少參數傳遞dist.assign(NODE,-1);//初始化距離為未知path.assign(NODE,-1);//初始化路徑為未知vector<bool>flag(NODE,0);//標志數組，判斷是否處理過dist[beg]=0;//出發點到自身路徑長度為0while(1){intv=-1;//初始化為未知for(inti=0;i!=NODE;++i)if(!flag[i]&&dist[i]>=0)//尋找未被處理過且if(v<0||dist[i]<dist[v])//距離最小的點v=i;if(v<0)return;//所有聯通的點都被處理過flag[v]=1;//標記for(inti=0;i!=NODE;++i)if(adjmap[v][i]>=0)//有聯通路徑且if(dist[i]<0||dist[v]+adjmap[v][i]<dist[i])//不滿足三角不等式{dist[i]=dist[v]+adjmap[v][i];//更新path[i]=v;//記錄路徑}}}intmain(){intn_num,e_num,beg;//含義見下cout<<輸入點數、邊數、出發點：;cin>>n_num>>e_num>>beg;vector<vector<int>>adjmap(n_num,vector<int>(n_num,-1));//默認初始化鄰接矩陣for(inti=0,p,q;i!=e_num;++i){cout<<輸入第<<i+1<<條邊的起點、終點、長度（負值代表不聯通）：;cin>>p>>q;cin>>adjmap[p][q];}vector<int>dist,path;//用於接收最短路徑長度及路徑各點dijkstra(beg,adjmap,dist,path);for(inti=0;i!=n_num;++i){cout<<beg<<到<<i<<的最短距離為<<dist[i]<<，反向列印路徑：;for(intw=i;path[w]>=0;w=path[w])cout<<w<<<-;cout<<beg<<' ';}}

❷ Dijkstra演算法求單源最短路徑

分給我，這是模板，很好用，我做acm用的

#define MAX 110
#define MAXVALUE 1000

int Cost[MAX][MAX],Dist[MAX];

void Dijkstra(int n,int v,int *Dist) //或 int Dist[MAX];
{
int newdist,i,j,temp,u;
bool s[MAX];

for(i=0;i<n;i++)
{
Dist[i]=Cost[v][i];
s[i]=false;
}

Dist[v]=0;
s[v]=true;

for(i=1;i<n;i++)
{
temp=MAXVALUE;
//u=v;
for(j=0;j<n;j++)
{
if((!s[j]) && (Dist[j]<temp))
{
u=j; temp=Dist[j];
}
}
s[u]=true;
for(j=0;j<n;j++)
{
if((!s[j]))// && (Cost[u][j]<MAXVALUE))
{
newdist=Dist[u]+Cost[u][j];
if(newdist<Dist[j]) Dist[j]=newdist;

}
}
}
return ;
}

❸ 如何證明求最短路勁的Dijkstra演算法的正確性

Dijkstra演算法（單源最短路徑）

單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優子結構性質。

一.最短路徑的最優子結構性質

該性質描述為：如果P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j的最短路徑，k和s是這條路徑上的一個中間頂點，那麼P(k,s)必定是從k到s的最短路徑。下面證明該性質的正確性。

假設P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那麼必定存在另一條從k到s的最短路徑P'(k,s)，那麼P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j的最短路徑相矛盾。因此該性質得證。

二.Dijkstra演算法

由上述性質可知，如果存在一條從i到j的最短路徑(Vi.....Vk,Vj)，Vk是Vj前面的一頂點。那麼(Vi...Vk)也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的演算法。譬如對於源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那麼當前已知可得從V0到達Vj頂點的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據這種思路，

假設存在G=<V,E>，源頂點為V0，U={V0},dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點。

1.從V-U中選擇使dist[i]值最小的頂點i，將i加入到U中；

2.更新與i直接相鄰頂點的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V，停止。

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

❺ Dijkstrath演算法是什麼如何用Dijkstrath演算法求計算機網路拓撲圖的最短路徑

Dijkstra演算法是典型 的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
迪傑斯特拉(Dijkstra)演算法思想
按路徑長度遞增次序產生最短路徑演算法：

把V分成兩組：

（1）S：已求出最短路徑的頂點的集合

（2）V-S=T：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑遞增的次序加入到S中，

保證：（1）從源點V0到S中各頂點的最短路徑長度都不大於

從V0到T中任何頂點的最短路徑長度

（2）每個頂點對應一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間

頂點的最短路徑長度

依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的

直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和

（反證法可證）

求最短路徑步驟
演算法步驟如下：

1. 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∝

2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的

距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

❻ 關於Dijkstra演算法

樓上正解，你找個圖自己用此演算法實踐一下就知道了，從A點出發，發現離A最近的點是B點，那麼我們就已經認為A到B的最短距離就是AB了，如果有負數，就指不定冒出個C點,AC+CB<AB;或者冒出個DE為很大的負值，AC+CD+DE+EF+FB<AB;等等諸如此類的情況。
簡單說來，你駕車從家出發到某地沿某條路只需經過一個收費站，但是遠在外省某地有個站不但不收你的費，你去了還會給你個千八百萬的歡迎光臨費，你能說你直接沿著這條路去某地是最省費用的？不計時間成本，繞到外省那個給你錢的地方，再繞回到你的目的地，還能賺錢呢。
而且一般權值為負的圖研究也比較少。有些帶負權的圖，某些點間還沒有最小距離呢。中間出個帶某條負權很大的邊的環圈，繞此一圈所經過的距離反而減少了，那就一直在此圈上繞啊繞啊繞到負的足夠大溢出為止。
當然考慮各種自己隨便假設出來的變種問題也是很有趣的。比如說邊帶有多個權值對應多次經過改變的消費，上面的問題有可能變成有解的。話說那個站會後悔，第二次經過它會收回100萬，第三次經過收回250萬，這樣的話你只需要經過一次就夠了，問題也是有解的。再比如說對於多權重圖，從A點出發經過B點到達C點的最短路線，就不是簡單的AB最短路線+BC最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^

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

}

}

(7)單源最短路徑dijkstra演算法擴展閱讀：

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

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

❽ Floyd演算法與Dijkstra演算法的區別

1、如果依次對某個頂點運用Dijkstra演算法，則與Floyd演算法相比，很多路徑和結果計算是重復的，雖然復雜度相同，但是運算量差了很多；

2、更為重要的是：Dijkstra演算法使用的前提是圖中路徑長度必須大於等於0；

但是Floyd演算法則僅僅要求沒有總和小於0的環路就可以了，因此Floyd 演算法應用范圍比Dijkstra演算法要廣。

❾ 計算機網路的最短路徑演算法有哪些對應哪些協議

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。

最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：

確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。

確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

全局最短路徑問題：求圖中所有的最短路徑。
Floyd

求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度O(V^3)。

Floyd-Warshall演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。
Floyd-Warshall演算法的時間復雜度為O(N^3)，空間復雜度為O(N^2)。

Floyd-Warshall的原理是動態規劃：

設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。

若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；

若最短路徑不經過點k，則Di,j,k = Di,j,k-1。

因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。

Floyd-Warshall演算法的描述如下：

for k ← 1 to n do

for i ← 1 to n do

for j ← 1 to n do

if (Di,k + Dk,j < Di,j) then

Di,j ← Di,k + Dk,j;

其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連接。

Dijkstra

求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）,可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。

當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
Bellman-Ford

求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間復雜度O（VE）。

Bellman-Ford演算法是求解單源最短路徑問題的一種演算法。

單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。

與Dijkstra演算法不同的是，在Bellman-Ford演算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環

路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而Bellman-Ford演算法具有分辨這種負環路的能力。
SPFA

是Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k< 與Bellman-ford演算法類似，SPFA演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA演算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
SPFA演算法可以用於存在負數邊權的圖，這與dijkstra演算法是不同的。

與Dijkstra演算法與Bellman-ford演算法都不同，SPFA的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為Bellman-ford演算法，其時間復雜度為O(VE)。
SPFA演算法在負邊權圖上可以完全取代Bellman-ford演算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法，以及它的使用堆優化的版本。通常的SPFA。