1.单源最短路：

介绍Dijstra算法之前先介绍单源最短路的概念吧!

而Dijstra算法常常用于解决单源最短路问题。

2.Dijstra算法简介：

a.Dijstra算法能够解决的问题：
常常用于计算一个顶点到其他所有顶点的最短路径。Dijstra算法的主要特点是以起点为中心，逐层向外扩展(这一点类似于bfs，但是不同的是，bfs每次扩展一个层(即扩展当前点能到达的点)，但是Dijstra每次只会扩张一个点)，每次都会取一个最近点继续扩展，直到取完所有的点为止。
注意：Dijstra算法要求图中不能出现负边权。（证明下面会给出）

b.Dijstra算法流程

c.Dijstra算法演示：

3.时间复杂度为O(n^2)代码(n为顶点数)

这里使用链表形式的邻接表存储图，效率过高，可以学习一下

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1001;  //点的个数 
const int M = 10001; //边的个数 struct edge {int v, w, next;  //v是指这条边指向的顶点,w是指这条边的长度为w,next是指与这条边同起点的上一条边是哪一条边edge(){}edge(int _v, int _w, int _next) {v = _v;w = _w;next = _next;}
} e[M * 2];int head[N], size;  //head数组记录以每个点为起点的最后一条边的编号，size 是目前有多少条边也是下一条边的编号void init() {memset(head, -1, sizeof(head));size = 0;
}void insert(int u, int v, int w) {   //插入边e[size] = edge(v, w, head[u]); //这条边终点是v,长度为d,同以 u 为起点的上一条边是之前以 u 为起点的最后一条边head[u] = size++;  //现在以 u 为起点的最后一条边就是这条边了
}void insert2(int u, int v, int w) {  //无向图保证插两次insert(u, v, w);insert(v, u, w);
}int n, m;int dis[N];   //记录源点到每个点的最短路 
bool vis[N]; //看这个点是否被标记 void dijkstra(int u) {memset(vis, false, sizeof(vis));memset(dis, 0x3f, sizeof(dis));  //初始化最大值dis[u] = 0;  //初始化源点for (int i = 0; i < n; ++i) {  //我们需要循环n次将每个点遍历int mind = 1000000000, minj = -1;  //mind表示当前最短路径, minj表示当前最短路径对应的顶点for (int j = 1; j <= n; ++j) {if (!vis[j] && dis[j] < mind) {  //找到了当前顶点能到达的点的最短路径,更新minj = j;mind = dis[j];}}if (minj == -1) {  //没有找到当前点最短的路径return ;}vis[minj] = true; //标记//下面当我们找到更新点后，我们需要在遍历更新的点能到达的边,更新这些点的权值for (int j = head[minj]; ~j; j = e[j].next) {int v = e[j].v;int w = e[j].w;if (!vis[v] && dis[v] > dis[minj] + w) {dis[v] = dis[minj] + w;}}}
}int main() {init();int u, v, w; //u,v,w代表顶点u到顶点v的边的权值为wcin >> n >> m; //n表示输入的顶点数, m表示输入的边数while (m --) {cin >> u >> v >> w; insert2(u, v, w);  //插入所输入的边}dijkstra(1);cout << dis[n] << endl;  //输出源点到第n个点的最短路径 return 0;
}

4.证明负边权导致Dijkstra算法不成立：

首先我们看上图，然后用上面说的算法流程来计算最短路
S代表源点
首先我们更新S能到达的点的最短路比如S能到达A和B那么S到A的最短路就是7,S
到B的最短路就是5，发现当前B点的路径最短，我们就遍历B能到达的点C更新C的最短路5 + 1 = 6发现6比S->A的最短路径7，然后遍历C访问到的点A，发现最短路径为6 + (-6) = 0，即更新S -> A的最短路，显然S -> A不可能最短路为0，则算法无法成立。

5.使用堆优化Dijkstra算法：

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {memset(p, -1, sizeof(p));eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边e[eid].v = v;e[eid].w = w;e[eid].next = p[u];p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边insert(u, v, w);insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {// 初始化 dist、小根堆和集合 Umemset(vst, 0, sizeof(vst));memset(dist, 0x3f, sizeof(dist));min_heap.insert(make_pair(0, s));dist[s] = 0;for (int i = 0; i < n; ++i) {if (min_heap.size() == 0) {  // 如果小根堆中没有可用顶点，说明有顶点无法从源点到达，算法结束return false;}// 获取堆顶元素，并将堆顶元素从堆中删除set<PII, less<PII> >::iterator iter = min_heap.begin();int v = iter->second;min_heap.erase(*iter);vst[v] = true;// 进行和普通 dijkstra 算法类似的松弛操作for (int j = p[v]; j != -1; j = e[j].next) {int x = e[j].v;if (!vst[x] && dist[v] + e[j].w < dist[x]) {// 先将对应的 pair 从堆中删除，再将更新后的 pair 插入堆min_heap.erase(make_pair(dist[x], x));dist[x] = dist[v] + e[j].w;min_heap.insert(make_pair(dist[x], x));}}}return true;  // 存储单源最短路的结果
}

欢迎关注:ly’s Blog