Dijkstra演算法
一.該演算法的背景和目的:
迪杰斯特拉演算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉演算法，
是從一個頂點到其余各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題，迪杰斯特拉演算法主要特點是從起始點開始，采用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，
二.基本思想：
如1.1這個圖 求其最短路徑（a是最初點）
將圖中頂點分為兩個集合，一個集合存放已求出初始到該點最短距離的點，另一個集合v存放其他各點，s集合的初始化里面有v0點(初始點a)
每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了）,
如圖1.2：
tips:v是在S里面的點 k是在U里面的點
1.若v與U中頂點u有邊，則(u,v)為正常權值，若u不是v的出邊鄰接點,則(u,v)權值 ∞(宏定義#define max INT_MAX);
2.從中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度），
3.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權，
4.重復步驟b和c直到所有頂點都包含在S中，
三.討論Dijkstra演算法基于的儲存結構
1.問題圖的存盤： 一般采用二維鄰接矩陣存盤
如該1.1圖存盤的的二維鄰接矩陣為
2.輔助陣列int 型別 updatedist[n] //不斷更新最近距離 （可以定義一個key和distance的結構體)
int類的：
struct型別：
這篇以int為主要討論的型別
3.輔助陣列 string型別 path[n] //存放初始點a到n的距離
如 path[1] 是存放 a到b點最短怎么走的路徑
path[2] 是存放 a到c點最短怎么走的路徑
path[3] 是存放 a到e點最短怎么走的路徑
path[4] 是存放 a到h點最短怎么走的路徑
4.集合s的表示
方法一：利用結構體的flag標記
方法二: 迭代完的點用updatedist[x]==0 來標記
四.寫的細碎的圖解(僅供參考)
直到updatedist陣列里面全是0，就全部迭代結束了
五.具體代碼實作
Dijkstra(int v，edge[][]) //從源點v出發
{
int i, k, num, dist[MaxSize];
string path[MaxSize];
for (i = 0; i < vertexNum; i++) //初始化陣列dist和path
{
dist[i] = edge[v][i];
if (dist[i] != 1000) //假設1000為邊上權的最大值
path[i] = vertex[v] + vertex[i]; //+為字串連接操作
else path[i] = "";
}
for (num = 1; num < vertexNum; num++)
{
k = Min(dist, vertexNum); //在dist陣列中找最小值并回傳其下標
cout << path[k] <<":" << dist[k] << endl;
for (i = 0; i < vertexNum; i++) //修改陣列dist和path
if (dist[i] > dist[k] + edge[k][i]) {
dist[i] = dist[k] + edge[k][i];
path[i] = path[k] + vertex[i]; //+為字串連接操作
}
dist[k] = 0; //將頂點k加到集合S中
}
}
傳入初始點和鄰接矩陣
int main(){
int n,e,v,edge[][];
cout<<"輸入起點下標："<<endl;
cin>>v;
cout<<"輸入圖的頂點數和邊數："<<endl;
cin>>n>>e;
//很具體的代碼我后續補充 就是構建二維陣列
return 0;
}
六.注意
這就是用鄰接矩陣實作dijkstra，但是這個演算法有一個壞處，就是出現負權邊，這個演算法就炸了，
1.不能出現負權邊
2.時間復雜度是o（n^2）
請大家批評指正！您批評的力度就是我成長的動力
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226848.html
標籤：其他