Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径（单源最短路径）。
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。 在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
假设a为起始点，a到a的最短路径是0，a到b的最短路径是1，a到c的最短路径是3，a到d的最短路径是8，a到e的最短路径是11。 用Dijkstra实现单源最短路： Dijkstra的思想是先初始化这样一张表（除了a之外，a到其他点的距离都是正无穷）： 在表中选择一个路径最短的点a，从a出发，a到自己的距离是0，它往外有三条边，更新a到b、c、d的最短距离，a这一点已经考察完了，以后a点不会被选到，此时表更新为：
在这张表中再选一个最短距离(a到b)，选出点b，它有两条边指向c和e，从a出发，若经过b到达c，则现在的距离是3，比之前从a直接到c大，所以更新最短距离，以后b点不会被选到，此时表更新为： 在这张表中再选一个最短距离(a到c)，选出c点，c往外有两条边，此时到e的距离为23(经过c)，比原来的51小，更新最短距离；此时到d的距离为8(经过c)，比原来的10小，更新最短距离，以后c点不会被选到，此时表更新为： 在这张表中再选一个最短距离(a到d)，选出d点，d往e有一条边，此时到e的距离为11(经过d)，更新最短距离，此时表更新为： 在这张表中再选一个最短距离(a到e)，它往外没有边，结束。所以这个表就是最后的结果，Dijkstra只有一个要求：不要出现权值加起来是负数的环即可。 权值是负数的话最短距离会变成负无穷(不停地转，最短距离会不断减小)，比如：
下面介绍一道模板题来实现这种基本的算法思想: POJ - 2387 Til the Cows Come Home 大概意思：输入总共有n个点的无向图的边数和权值，求出从起点1到点n的最短距离。
如果是一个稀疏图的话，比如说n是10 ^ 5，两层循环的话程序可能会爆掉，所以我们要对其进行优化。在寻找一个顶点加入已求出最短路径顶点的集合时(找到一个还没进入最短路径的顶点集合的点，这个点离起点的最短路径最小)，这个过程的时间复杂度为：O(n)；接下来用dist[t]更新未确定最短路径的顶点，这个过程的时间复杂度为：O(m)，m小于等于n，这两个过程都要循环n遍，所以总的时间复杂度为O(n ^ 2)。 在一堆数里面找一个最小的数，可以用堆的数据结构，在堆里面修改一个数的时间复杂度是O(log n)，所以用dist[t]更新未确定最短路径的顶点的总时间复杂度：O(m * logn)。 堆有两种实现方式，一种是手写堆，手写堆的好处是我们时刻可以保证堆里面只有n个数；另外一种是用优先队列实现，用c++里面的priority_queue，优先队列是不支持修改任意一个元素的操作，它的实现方式是每一次修改都往队列里插一个新的数，可能会有一些数冗余，但使用优先队列比较好写，假设元素个数变成m，总的时间复杂度会变成O(m * logm)，但一般来说，m < n ^ 2，所以logm是小于log(n ^ 2)，而log(n ^ 2) = 2logn，所以logm和logn其实是同个级别的，所以我们可以直接把用优先队列的总时间复杂度看成是O(m * logn)。所以一般来说dijkstra算法我们是不用手写堆来实现，直接用c++里面的priority_queue就可以了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } typedef pair<int, int> PII; const int N = 4005; //先把存储方式改成邻接表的形式 int n, m, h[N], w[N], e[N], ne[N], idx, dist[N], st[N]; //w数组表示的是权重(两点间的距离) , st数组记录某点是否被弹出过队列(已求得最短距离) void add(int a, int b, int c){ //加边的模板 e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int dijkstra(){ int ver, distance, i, j; memset(dist, 0x3f, sizeof(dist)); //初始化距离为正无穷 dist[1] = 0; priority_queue <PII, vector<PII>, greater<PII> > heap; //用优先队列维护所有的距离 heap.push({0, 1}); //把一号点放进去以更新后续所有的点 while(heap.size()){ PII t = heap.top(); //找到当前最小的点，即小根堆的起点 heap.pop(); ver = t.second; //ver表示点的编号 if(st[ver]) continue; //假如ver这个点之前已经被弹出过 (已求得最短距离), 直接continue st[ver] = 1; //标记ver这个点已求得最短路径，后续用这个点来更新其他未求得最短路径的点 当前它们的最短路径 for(i = h[ver]; i != -1; i = ne[i]){ //遍历ver这个点所有的邻边 j = e[i]; //用j来储存邻边连接某点的编号 if(dist[j] > dist[ver] + w[i]){ //更新的条件判断跟朴素的dijkstra算法一样 dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); //把点j以及求得的当前最短距离放进优先队列 } } } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main(){ int a, b, c; m = read(); n = read(); memset(h, -1, sizeof(h)); //把表头初始化为空 while(m--){ a = read(); b = read(); c = read(); add(a, b, c); //用邻接表存储的话出现重边也无所谓了，优先队列会保证我们选的是最短的边，所以就不用对重边做特殊的处理了 add(b, a, c); } printf("%d\n", dijkstra()); return 0; }下面再介绍一道模板题来实现这种基本的算法思想： P3371 【模板】单源最短路径（弱化版） 大概意思：给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 调用c++自带的优先队列（详细见注释）：
#include<bits/stdc++.h> using namespace std; #define maxn 10005 #define maxm 500005 #define INF 2147483647 int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } struct Edge{ int u, v, w, next; }e[maxm]; int head[maxn], cnt, n, m, s, vis[maxn], dis[maxn]; struct node{ int w, now; inline bool operator <(const node &x)const{ //重载运算符把最小的元素放在堆顶（大根堆） return w > x.w; //这里注意符号要为'>' } }; priority_queue <node> q; //优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体 void add(int u, int v, int w){ e[++cnt].u = u; //这句话对于此题不需要，但在缩点之类的问题还是有用的 e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; //存储该点的下一条边 head[u] = cnt;//更新目前该点的最后一条边（就是这一条边） } //链式前向星加边 void dijkstra(){ for(int i = 1; i <= n; i++) dis[i] = INF; dis[s] = 0;//赋初值 q.push((node){0, s}); while(!q.empty()){ //堆为空即为所有点都更新 node x = q.top(); q.pop(); int u = x.now; //记录堆顶（堆内最小的边）并将其弹出 if(vis[u]) continue; //没有遍历过才需要遍历 vis[u] = 1; for(int i = head[u]; i; i = e[i].next){ //搜索堆顶所有连边 int v = e[i].v; if(dis[v] > dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; //松弛操作 q.push((node){dis[v], v}); //把新遍历到的点加入堆中 } } } } int main(){ int i, x, y, z; n = read(); m = read(); s = read(); for(i = 1; i <= m; i++){ x = read(); y = read(); z = read(); add(x, y, z); } dijkstra(); for(i = 1; i <= n; i++) printf("%d ",dis[i]); return 0; }