求是单源最短路径，即给定一个源点，求其到其他顶点的最短路径。Dijkstra算法就是解决它的，而其前提条件是图中每条边的权重不为负值。
朴素版用于处理稠密图，使用邻接矩阵存储图；优化版用于处理稀疏图，使用邻接表存储图。
朴素版
题目链接：Dijkstra求最短路 I
思路
集合S为已经确定最短路径的点集。
- 初始化距离：一号结点的距离为零，其他结点的距离设为无穷大。
- 循环n次（n为顶点数），每一次将集合S之外距离最短的点T（dist值最小）加入到S中去（这里的距离最短指的是距离1号点最近。点T的路径一定最短，基于贪心）。然后用点T更新T的邻接点的距离。
C++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];
int dist[N];
bool flag[N];
int n, m;
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化所有离源点的距离为无穷大
dist[1] = 0; // 源点离自身的距离为0
for (int i = 1; i <= n; i++)
{
int t = -1;
// 找到未确定到源点距离的点中dist值最小的那个点
for (int j = 1; j <= n; j++)
if (!flag[j] && (t == -1 || dist[t] > dist[j]))
t = j;
flag[t] = true; // 接下来确定这个点到源点的距离
// 更新其他未确定的并于点t的连通的点的dist值
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n]; // 如果汇点（终点）的值不为无穷大，则说明其于源点连通，返回其dist值
}
int main()
{
cin.tie(0);
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m --)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z); // 重边和自环可以通过取最小权重来解决
}
cout << dijkstra() << endl;
return 0;
}
Python
n, m = map(int, input().split())
maxdist = float("inf")
g = [[maxdist] * (n + 1) for _ in range(n + 1)]
flag = [False] * (n + 1)
dist = [maxdist] * (n + 1)
for _ in range(m):
x, y, z = map(int, input().split())
g[x][y] = min(g[x][y], z)
def dijkstra():
dist[1] = 0
for i in range(1, n + 1):
t = -1
for j in range(1, n + 1):
if not flag[j] and (t == -1 or dist[t] > dist[j]):
t = j
flag[t] = True
for j in range(1, n + 1):
dist[j] = min(dist[j], dist[t] + g[t][j])
return dist[n] if dist[n] < maxdist else -1
print(dijkstra())
优化版
题目链接：Dijkstra求最短路 II
思路
堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化为O(logn)。
- 一号点的距离初始化为零，其他点初始化成无穷大。
- 将一号点放入堆中。
- 不断循环，直到堆空。每一次循环中执行的操作为：
弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
用该点更新临界点的距离，若更新成功就加入到堆中。
C++
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
int n, m;
int idx = 0;
int h[N], ne[N], val[N], w[N];
int dist[N];
bool flag[N];
void add(int x, int y, int z)
{
w[idx] = z;
val[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
int dijkstra2()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({ 0, 1 });
while (pq.size())
{
PII k = pq.top();
pq.pop();
int ver = k.second, distance = k.first;
if (flag[ver]) continue;
flag[ver] = true;
// 稀疏图使用邻接表的方式，在这里遍历时的时间复杂度要更低
// 对于当前选中的顶点ver，遍历与该点连通的顶点
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = val[i]; // i只是顶点的一个编号，而val[i]代表的才是其顶点
// 更新与顶点ver连通的顶点的dist值
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
pq.push({ dist[j], j }); // 加入优先队列
}
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z); // 对于用邻接表存储的图，构建图时可以不用特殊处理重边和自环
}
cout << dijkstra2() << endl;
return 0;
}