cdijkstra演算法
Dijkstra演算法是尋找最短路徑的一種搜索演算法，由荷蘭科學家提出。
演算法描述：通過為每個節點保留目前為止所找到的從s到e的最短路徑。為了記錄最佳路徑軌跡，記錄路徑上每個節點的前趨，通過回溯法找出最短路徑軌跡。
在網上搜索一些版本的Matlab實現方法，感覺都有些毛病。經過修改，得到比較好的效果。
[cpp] view plain
function [ distance path] = Dijk( W,st,e )
%DIJK Summary of this function goes here
% W 權值矩陣 st 搜索的起點 e 搜索的終點
n=length(W);%節點數
D = W(st,:);
visit= ones(1:n); visit(st)=0;
parent = zeros(1,n);%記錄每個節點的上一個節點
path =[];
for i=1:n-1
temp = [];
%從起點出發，找最短距離的下一個點，每次不會重復原來的軌跡，設置visit判斷節點是否訪問
for j=1:n
if visit(j)
temp =[temp D(j)];
else
temp =[temp inf];
end
end
[value,index] = min(temp);
visit(index) = 0;
%更新 如果經過index節點，從起點到每個節點的路徑長度更小，則更新，記錄前趨節點，方便後面回溯循跡
for k=1:n
if D(k)>D(index)+W(index,k)
D(k) = D(index)+W(index,k);
parent(k) = index;
end
end
end
distance = D(e);%最短距離
%回溯法 從尾部往前尋找搜索路徑
t = e;
while t~=st && t>0
path =[t,path];
p=parent(t);t=p;
end
path =[st,path];%最短路徑
end
測試：
測試用例1
[cpp] view plain
W=[0 50 inf 40 25 10
50 0 15 20 inf 25
inf 15 0 10 20 inf
40 20 10 0 10 25
25 inf 20 10 0 55
10 25 inf 25 55 0];
[cpp] view plain
[cpp] view plain
[distance,path]=Dijk(W,1,4);
>> distance
distance =
35
>> path
path =
1 6 4
從節點1到節點4最短距離路徑為1-->6-->4, 最短距離為35
⑵ 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演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。
其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。
不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。
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到任何其他頂點的最短路徑。
⑷ Dijkstra 演算法是什麼
迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。
對於圖G=（V，E），將圖中的頂點分成兩組：
第一組S：已求出的最短路徑的終點集合（開始為{v0}）。
第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。
演算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。
【演算法思想】
g為用鄰接矩陣表示的帶權圖。
（1）S<-{v0};
dist[i]=g.arcs[v0][v1].adj;(vi屬於V-S)(將v0到其餘頂點的最短路徑長度初始化為權值)
（2）選擇vk,使得：dist[k]=min(dist[i]|vi屬於V-S)vk為目前求得的下一條從v0出發的最短路徑的終點。
（3）將vk加入S；
（4）修正從v0出發到集合V-S上任一頂點vi的最短路徑長度：從v0出發到集合V-S上任一頂點vi的當前最短路徑的長度為dist[i]，從v0出發，中間經過新加入S的vk，然後到達集合V-S上任一頂點vi的路徑長度為：dist[k]+g.arcs[k][i].adj
如果：dist[k]+g.arcs[k][i].adj<dist[i]
則dist[i]=dist[k]+g.arcs[k][i].adj
（5）重復（2）~（4）n-1次，即可按最短路徑長度的遞增順序，逐個求出v0到圖中其餘每個頂點的最短路徑。
【演算法描述】
typedef unsigned int WeightType;
typedef WeightType AdjType;
typedef SeqList VertexSet;
ShortestPath_DJS(AdjMatrix g,int v0,WeightType dist[MAX_VERTEX_NUM],VertexSet path[MAX_VERTEX_NUM])
/* path[i]中存放頂點i的當前最短路徑。dist[i]中存放頂點i的當前最短路徑長度*/
{
VertexSet s; /* s為已找到最短路徑的終點集合 */
for(i=0;i<g.vexnum;i++) /* 初始化dist[i]和path [i] */
{
InitList(&path[i]);
dist[i]=g.arcs[v0][i].adj;
if(dist[i]<INFINITY)
{
AddTail(&path[i],g.vexs[v0]); /* AddTail為表尾添加操作*/
AddTail(&path[i],g.vexs[i]);
}
}
InitList(&s);
AddTail(&s,g.vexs[v0]); /* 將v0看成第一個已找到最短路徑的終點*/
/*以上部分完成了對向量最短路徑長度dist[ ]，路徑path[],頂點集s[]的初始化工作*/
/*以下部分通過n-1次循環，將第二組頂點集V-S中的頂點按照遞增有序方式加入到S集合中，並求得從頂點v0出發到達圖中其餘頂點的最短路徑。*/
for(t=1;t<=g.vexnum-1;t++) /*求v0到其餘n-1個頂點的最短路徑(n= g.vexnum )*/
{
min=INFINITY;
for(i=0;i<g.vexnum;i++)
if(!Member(g.vex[i],s)&&dist[i]<min)
{
k =i;
min=dist[i];
}
AddTail(&s,g.vexs[k]);
for(i=0;i<g.vexnum;i++) /*修正dist[i], i∈V-S*/
if(!Member(g.vex[i],s)&&g.arcs[k][i].adj!=INFINITY&&(dist[k]+g.arcs[k][i].adj<dist[i]))
{
dist[i]=dist[k]+g.arcs[k][i].adj;
path[i]=path[k];
AddTail(&path[i],g.vexs[i]); /* path[i]=path[k]∪{Vi} */
}
}
}
另外說一下，該演算法的時間復雜度很明顯，為O（n^2）。
⑸ Prim和Dijkstra演算法的區別
在圖論中，Prim演算法是計算最小生成樹的演算法，而Dijkstra演算法是計算最短路徑的演算法。二者看起來比較類似，因為假設全部頂點的集合是V，已經被挑選出來的點的集合是U，那麼二者都是從集合V-U中不斷的挑選權值最低的點加入U。
二者的不同之處在於「權值最低」的定義不同，Prim的「權值最低」是相對於U中的任意一點而言的，也就是把U中的點看成一個整體，每次尋找V-U中跟U的距離最小（也就是跟U中任意一點的距離最小）的一點加入U；而Dijkstra的「權值最低」是相對於v0而言的，也就是每次尋找V-U中跟v0的距離最小的一點加入U。
一個可以說明二者不等價的例子是有四個頂點(v0, v1, v2, v3)和四條邊且邊值定義為(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的圖，用Prim演算法得到的最小生成樹中v0跟v1是不直接相連的，也就是在最小生成樹中v0v1的距離是v0->v2->v3->v1的距離是27，而用Dijkstra演算法得到的v0v1的距離是20，也就是二者直接連線的長度。
⑹ Dijkstra演算法
這是我自己寫的一個簡單的DIJKSTRA演算法，其中測試數據是
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
結構清晰簡單，對於你要搞懂這個演算法很有幫助。有不懂的可以問我：我的QQ是396730783
#include"stdio.h"
#define MAX 100000000
int main()
{
int map[101][101];
int dis[101];
int a,b,c;
int i,j,k,n,m;
int min;
while(scanf("%d",&n)==1)
{
int final[101] = {0};
scanf("%d",&m);
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
map[i][j] = map[j][i] = MAX;
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = c;
}
for(i=1;i<n;i++)
{
dis[i] = map[0][i];
}
dis[0] = 0;
final[0] = 1;
for(i=0;i<n-1;i++)
{
min = MAX;
for(j=1;j<n;j++)
{
if(!final[j] && min > dis[j])
{
min = dis[j];
k = j;
}
}
final[k]=1;
for(j=1;j<n;j++)
{
if(!final[j] && dis[k]+map[k][j]<dis[j])
dis[j] = dis[k]+map[k][j];
}
}
for(i=1;i<n;i++)
{
if(dis[i] == MAX)
printf("不可通");
else
printf("%5d",dis[i]);
}
printf("\n");
}
return 0;
}
⑺ 解釋一下dijkstra演算法這個計算過程的意思 怎麼算的
最近也看到這個演算法，不過主要是通過C語言介紹的，不太一樣，但基本思想差不多。下面只是我個人的看法不一定準確。
Dijkstra演算法主要解決指定某點(源點)到其他頂點的最短路徑問題。
基本思想：每次找到離源點最近的頂點，然後以該頂點為中心(過渡頂點)，最終找到源點到其餘頂點的最短路。
t=1：令源點(v_0)的標號為永久標號(0,λ)(右上角加點), 其他為臨時(+無窮,λ). 就是說v_0到v_0的距離是0，其他頂點到v_0的距離為+無窮。t=1時，例5.3上面的步驟(2)(3)並不能體現
t=2：第1步v_0(k=0)獲得永久標號，記L_j為頂點標號當前的最短距離(比如v_0標號(0,λ)中L_0=0), 邊(v_k,v_j)的權w_kj. 步驟(2)最關鍵，若v_0與v_j之間存在邊，則比較L_k+w_kj與L_j, 而L_k+w_kj=L_0+w_0j<L_j=+無窮。
這里只有v_1,v_2與v_0存在邊，所以當j=1,2時修改標號, 標號分別為(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不變。步驟(3)比較所有臨時標號中L_j最小的頂點, 這里L_1=1最小，v_1獲得永久標號(右上角加點)。
t=3: 第2步中v_1獲得永久標號(k=1), 同第2步一樣，通過例5.3上面的步驟(2)(3)，得到永久標號。 步驟(2),若v_1與v_j(j=2,3,4,5(除去獲得永久標號的頂點))之間存在邊，則比較L_1+w_1j與L_j。這里v_1與v_2，v_3，v_,4存在邊，
對於v_2, L_1+w_12=1+2=3<L_2=4, 把v_2標號修改為(L_1+w_12, v_1)=(3, v_1);
對於v_3, L_1+w_13=1+7=8<L_3=+無窮, 把v_3標號修改為(L_1+w_13, v_1)=(8, v_1);
對於v_4, L_1+w_14=1+5=6<L_4=+無窮, 把v_4標號修改為(L_1+w_14, v_1)=(6, v_1);
v_5與v_1不存在邊，標號不變。步驟(3), 找這些標號L_j最小的頂點，這里v_2標號最小
t=4: k=2, 與v_2存在邊的未獲得永久標號的頂點只有v_4, 比較L_2+w_24=3+1=4<L_4=6, 把v_4標號修改為(L_2+w_24, v_2)=(4, v_2); 其他不變。步驟(3), L_4=4最小。
t=5: k=4, 同理先找v_4鄰接頂點，比較，修改標號，找L_j最小
t=6: 同理
啰嗦的這么多，其實步驟(2)是關鍵，就是通過比較更新最短路徑，右上角標點的就是距離源點最近的頂點，之後每一步就添加一個新的」源點」，再找其他頂點與它的最短距離。
迪傑斯特拉演算法(Dijkstra)(網路)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
裡面有個動圖，更形象地說明了該演算法的過程。(其中每次標注的一個紅色頂點out就和你的這本書中獲得永久標號是相似的)
⑻ 最短路徑的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<<'
';}}