Dijkstra算法：
普通实现复杂度O(n^2) BinaryHeaps优化的是O(mlogn) Fib堆优化的是O（m+nlogn） m是图的边数，n是图的点数
特点： 基本思想是贪心思想，对于每个节点v[i]，维护估计最短路长度最大值 每次取出一个使得该估计值最小的t，并采用与t相连的边对其余点的估计值进行更新，更新后不再考虑t。在此过程中，估计值单调递减，所以可以得到确切的最短路。
使用松弛技术，
优点： 简单，实现快速！ 具有贪心算法的特性：最短路径的子路径是最短路径！ 相比于和他同类型的Bellman ford，它更快，缺点是边权值非负。
缺点： 边的权值必须为非负，Dijkstra算法假定输入图中的所有边的权值都是非负的
朴素Dijkstra算法实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 329999 //定义此图的最大距离
#define MaxN 100 //一个图最大的点数
int cost[MaxN][MaxN]; //此为Dijkstra的数组实现，复杂度为O(n^2)
int pathCon[MaxN]; //记录最短路径获得的时候的前向节点 路径重建
int pathDis[MaxN]; //路径距离
int vis[MaxN]; //标记是否结束访问
void Dijkstra(int n, int root)
{
memset(vis, 0, sizeof(vis)); //标记vis为全部未访问
vis[root] = 1; //标记root已访问
for (int i=0; i<n; i++)
pathDis[i] = cost[root][i], pathCon[i] = root;
pathDis[root] = 0; pathCon[root] = -1; // 树根的标记
int pre = root;
for (int i=1; i<n; i++) //遍历剩下的n-1个点，每执行一次能够确定一个点的最短距离
{
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) //初始化构建矩阵的时候，不相邻元素距离为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]; //构建每条最短路径
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个点，所以n是5
{
init(5);
Dijkstra(5,0);
reshape(5,0);
}
加入优先队列优化的Dijkstra算法：
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// Dijkstra O(m*log n)
#define MaxN 100 //一个图最大的点数
#define MaxM 1000 //一个图最大的边数
#define V MaxN
#define E MaxM
#define INF 329999 //定义此图的最大距离
#define typec int // type of cost
typec cost[E], pathDis[V]; // cost[E] 每条边的代价 pathDis[V]最短路径的值
int e, pnt[E], cluster[E], head[V];
int pathCon[V], vis[V];
/*
pnt[] 保存每条边的终点
cost[] 保存每条边的权值
cluster[] 把边按照起始点聚类
head[u] u号节点的边结束边序号
*/
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++) //循环n次
{
for (int j = head[pre]; j != -1; j = cluster[j]) //展开节点
{
int k = pnt[j]; //j为边索引号
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为点数， m 为边数
{
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]; //构建每条最短路径
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);
}
上述实现的图是：
用LatexDraw 画的图，效果还可以。。。