Dijkstra算法：
普通實(shí)現(xiàn)復(fù)雜度O(n^2) BinaryHeaps優(yōu)化的是O(mlogn) Fib堆優(yōu)化的是O（m+nlogn） m是圖的邊數(shù)，n是圖的點(diǎn)數(shù)
特點(diǎn)： 基本思想是貪心思想，對(duì)于每個(gè)節(jié)點(diǎn)v[i]，維護(hù)估計(jì)最短路長度最大值 每次取出一個(gè)使得該估計(jì)值最小的t，并采用與t相連的邊對(duì)其余點(diǎn)的估計(jì)值進(jìn)行更新，更新后不再考慮t。在此過程中，估計(jì)值單調(diào)遞減，所以可以得到確切的最短路。
使用松弛技術(shù)，
優(yōu)點(diǎn)： 簡單，實(shí)現(xiàn)快速！ 具有貪心算法的特性：最短路徑的子路徑是最短路徑！ 相比于和他同類型的Bellman ford，它更快，缺點(diǎn)是邊權(quán)值非負(fù)。
缺點(diǎn)： 邊的權(quán)值必須為非負(fù)，Dijkstra算法假定輸入圖中的所有邊的權(quán)值都是非負(fù)的
樸素Dijkstra算法實(shí)現(xiàn)：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 329999 //定義此圖的最大距離
#define MaxN 100 //一個(gè)圖最大的點(diǎn)數(shù)
int cost[MaxN][MaxN]; //此為Dijkstra的數(shù)組實(shí)現(xiàn)，復(fù)雜度為O(n^2)
int pathCon[MaxN]; //記錄最短路徑獲得的時(shí)候的前向節(jié)點(diǎn) 路徑重建
int pathDis[MaxN]; //路徑距離
int vis[MaxN]; //標(biāo)記是否結(jié)束訪問
void Dijkstra(int n, int root)
{
memset(vis, 0, sizeof(vis)); //標(biāo)記vis為全部未訪問
vis[root] = 1; //標(biāo)記root已訪問
for (int i=0; i<n; i++)
pathDis[i] = cost[root][i], pathCon[i] = root;
pathDis[root] = 0; pathCon[root] = -1; // 樹根的標(biāo)記
int pre = root;
for (int i=1; i<n; i++) //遍歷剩下的n-1個(gè)點(diǎn)，每執(zhí)行一次能夠確定一個(gè)點(diǎn)的最短距離
{
int Min = INF;
for (int j=0; j<n; j++)
{
if (vis[j]==0 && cost[pre][j]!=INF && pathDis[pre]+cost[pre][j]<pathDis[j])
pathDis[j] = pathDis[pre] + cost[pre][j],pathCon[j] = pre;
}
for (int j=0; j<n; j++)
{
if (vis[j] == 0 && pathDis[j] < Min)
Min = pathDis[j], pre = j;
}
vis[pre] = 1;
}
}
void init(int n) //初始化構(gòu)建矩陣的時(shí)候，不相鄰元素距離為INF,自身到自身距離為0
{
//n=4
cost[0][0]=0, cost[0][1]=5,cost[0][2]=1, cost[0][3]=4, cost[0][4]=INF;
cost[1][0]=5, cost[1][1]=0,cost[1][2]=3, cost[1][3]=1, cost[1][4]=2;
cost[2][0]=1, cost[2][1]=3,cost[2][2]=0, cost[2][3]=INF,cost[2][4]=6;
cost[3][0]=4, cost[3][1]=1,cost[3][2]=INF,cost[3][3]=0, cost[3][4]=3;
cost[4][0]=INF,cost[4][1]=2,cost[4][2]=6, cost[4][3]=3, cost[4][4]=0;
}
void reshape(int n,int root)
{
for(int i=0;i<n;i++)
{
if(pathDis[i]==INF) cout<<"node "<<root<<" to node "<<i<<"is INF"<<endl;
else cout<<"node "<<root<<" to node "<<i<<"is "<<pathDis[i]<<endl;
}
vector<int> Path[MaxN]; //構(gòu)建每條最短路徑
for(int i=n-1;i>=0;i--)
{
vector<int> temp;
int j=i;temp.push_back(j);
while(pathCon[j]!=-1)
{
temp.push_back(pathCon[j]);
j=pathCon[j];
}
reverse(temp.begin(),temp.end());
Path[i]=temp;
}
for(int i=0;i<n;i++)
{
cout<<"Path "<<root<<" "<<"to "<<i<<" is ";
for(int j=0;j<Path[i].size();j++)
cout<<Path[i][j]<<" ";
cout<<endl;
}
}
int main() //n個(gè)點(diǎn)，所以n是5
{
init(5);
Dijkstra(5,0);
reshape(5,0);
}
加入優(yōu)先隊(duì)列優(yōu)化的Dijkstra算法：
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// Dijkstra O(m*log n)
#define MaxN 100 //一個(gè)圖最大的點(diǎn)數(shù)
#define MaxM 1000 //一個(gè)圖最大的邊數(shù)
#define V MaxN
#define E MaxM
#define INF 329999 //定義此圖的最大距離
#define typec int // type of cost
typec cost[E], pathDis[V]; // cost[E] 每條邊的代價(jià) pathDis[V]最短路徑的值
int e, pnt[E], cluster[E], head[V];
int pathCon[V], vis[V];
/*
pnt[] 保存每條邊的終點(diǎn)
cost[] 保存每條邊的權(quán)值
cluster[] 把邊按照起始點(diǎn)聚類
head[u] u號(hào)節(jié)點(diǎn)的邊結(jié)束邊序號(hào)
*/
struct qnode {
int v; typec c;
qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
bool operator < (const qnode& r) const { return c>r.c; }
};
void dijkstra(int n, const int root)
{
qnode mv;
priority_queue<qnode> que;
vis[root] = 1; pathDis[root] = 0;
que.push(qnode(root, 0));
for (int pre = root, i=1; i<n; i++) //循環(huán)n次
{
for (int j = head[pre]; j != -1; j = cluster[j]) //展開節(jié)點(diǎn)
{
int k = pnt[j]; //j為邊索引號(hào)
if (vis[k] == 0 &&
pathDis[pre] + cost[j] < pathDis[k])
{
pathDis[k] = pathDis[pre] + cost[j];
que.push(qnode(pnt[j], pathDis[k]));
pathCon[k] = pre;
}
}
while (!que.empty() && vis[que.top().v] == 1)
que.pop();
if (que.empty()) break;
mv = que.top(); que.pop();
vis[pre = mv.v] = 1;
}
}
inline void addedge(int u, int v, typec c){
pnt[e] = v; cost[e] = c; cluster[e] = head[u]; head[u] = e++;
}
void init(int n, int m) //n為點(diǎn)數(shù)， m 為邊數(shù)
{
int i, u, v; typec c;
e = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(pathCon, -1, sizeof(pathCon));
for (i = 0; i < n; i++) pathDis[i] = INF;
//for (i = 0; i < n; ++i)
//{
//scanf("%d%d%d", &u, &v, &c); // %d: type of cost
//addedge(u, v, c); // 這里添加的是單向邊，如果題目描述不同，需要加入addedge(v,u,c);
//}
addedge(0,2,1);
addedge(2,0,1);
addedge(0,1,4);
addedge(1,0,4);
addedge(1,3,1);
addedge(3,1,1);
addedge(2,3,4);
addedge(3,2,4);
addedge(2,4,2);
addedge(4,2,2);
addedge(3,5,2);
addedge(6,3,2);
addedge(4,5,3);
addedge(5,4,3);
}
void reshape(int n,int root)
{
for(int i=0;i<n;i++)
{
if(pathDis[i]==INF) cout<<"node "<<root<<" to node "<<i<<"is INF"<<endl;
else cout<<"node "<<root<<" to node "<<i<<"is "<<pathDis[i]<<endl;
}
vector<int> Path[MaxN]; //構(gòu)建每條最短路徑
for(int i=n-1;i>=0;i--)
{
vector<int> temp;
int j=i;temp.push_back(j);
while(pathCon[j]!=-1)
{
temp.push_back(pathCon[j]);
j=pathCon[j];
}
reverse(temp.begin(),temp.end());
Path[i]=temp;
}
for(int i=0;i<n;i++)
{
cout<<"Path "<<root<<" "<<"to "<<i<<" is ";
for(int j=0;j<Path[i].size();j++)
cout<<Path[i][j]<<" ";
cout<<endl;
}
}
int main()
{
init(6,7); //n = 6 m = 7
dijkstra(6, 3);
reshape(6,3);
}
上述實(shí)現(xiàn)的圖是：
用LatexDraw 畫的圖，效果還可以。。。