将结点分成两个集合：已确定最短路长度的点集（记为$S$ 集合）的和未确定最短路长度的点集（记为$T$ 集合）。一开始所有的点都属于$T$集合。初始化$dis(s) = 0$，其他点的均为$INF$。
然后重复这些操作：
直到 $T$ 集合为空，算法结束。
暴力：
不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在 $T$ 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为$O(m)$ ，1 操作总时间复杂度为$O(n^2)$ ，全过程的时间复杂度为 $O(n^2)$。
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
void dijkstra(int n, int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for (int i = 1; i <= n; i++) {
int u = 0, mind = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[j] < mind)
u = j, mind = dis[j];
vis[u] = true;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w;
}
}
}
// 邻接矩阵
#define N 505
#define INF 0x3f3f3f3f
int g[N][N]; // memset(g, 0x3f, sizeof(g));
int dis[N], vis[N];
void dijkstra(int n, int s) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
for (int i = 0; i < n; i++) {
int u = 0, mind = INF;
for (int j = 0; j < n; j++)
if (!vis[j] && dis[j] < mind)
u = j, mind = dis[j];
vis[u] = 1;
for (int v = 0; v < n; v++) {
if (v == u) continue;
if (dis[v] > dis[u] + g[u][v])
dis[v] = dis[u] + g[u][v];
}
}
}
优先队列：
和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 $O(m)$ 的，时间复杂度为 $O(mlogm)$。
struct edge {
int v, w;
};
struct Node {
int dis, u;
bool operator<(const Node& o) const { return dis > o.dis; }
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<Node> q;
void dijkstra(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
二叉堆：
维护$n$个元素的小根堆，对于更新图中点$i$的最短路，我们直接定位到这个点在堆数组$dis$中的位置$mp[i]$并对其采取上浮操作。保证每个元素只在堆中存在一次。而在优先队列优化中，一个点可能会多次进入队列。
const int INF = 0x3f3f3f3f;
template <int PMAX = 105, int EMAX = 10005>
struct Dijkstra {
int ecnt;
struct Edge {
int to, w, next;
} edge[EMAX];//边集
int head[PMAX];//head[i], i点出边链表
void init() {
for (int i = 0; i < PMAX; i++) head[i] = -1;
ecnt = 0;
}
void add_edge(int u, int v, int w) {
edge[ecnt].to = v; //终点
edge[ecnt].w = w; //权值
edge[ecnt].next = head[u];
head[u] = ecnt++;
/*
before
head[u] -> v1 -> v2 -> ... -> -1
after
head[u] -> v -> v1 -> v2 -> ... -> -1
*/
}
/*
for (int j = head[i]; j != -1; j = edge[j].next) //遍历i点的出边
printf("%d %d\\n", edge[j].to, edge[j].w);
*/
// mp[i] 图上节点i，对应的堆中的下标
// o[i] 堆中下标i，对应的图上节点编号
int dis[PMAX], o[PMAX], mp[PMAX]; // o[i] = j, mp[j] = i
int hsz;
// 交换堆中p1和p2下标的值
void swap(int p1, int p2) {
int t = dis[p1];
dis[p1] = dis[p2];
dis[p2] = t;
t = o[p1];
o[p1] = o[p2];
o[p2] = t;
mp[o[p1]] = p1;
mp[o[p2]] = p2;
}
// 下沉
void h_down_node(int pos) {
for (int i=pos*2+1; i<hsz; pos=i, i=i*2+1) {
if (i+1<hsz && dis[i] > dis[i+1]) i = i+1;
if (dis[pos] > dis[i]) {
swap(pos, i);
} else break;
}
}
// 上浮
void h_up_node(int pos) {
while (pos && dis[pos-1>>1] > dis[pos]) {
swap(pos, pos-1>>1);
pos = pos-1>>1;
}
}
// 删除堆顶
void heap_pop() {
assert(hsz>0);
swap(0, --hsz);
h_down_node(0);
}
// n个点，从s出发
void dijkstra(int n, int s) {
// 用小根堆维护dis
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for (int i=0; i<n; i++) mp[i] = o[i] = i;
hsz = n;
// 初始化n个元素的堆，只有mp[s]是0,其他是无穷大，直接上浮mp[s]
h_up_node(s);
while (hsz) {
int u = o[0];
heap_pop();
for (int j = head[u]; j != -1; j = edge[j].next) {
int v = edge[j].to, w = edge[j].w;
if (mp[v] < hsz && dis[mp[v]] > dis[mp[u]] + w) {
dis[mp[v]] = dis[mp[u]] + w;
h_up_node(mp[v]);
}
}
}
// for (int i=0; i<n; i++) {
// cout << i << " = " << dis[mp[i]] << endl;
// }
}
Dijkstra() {
init();
}
};
多源最短路，求任意两个结点之间的最短路。时间复杂度$O(n^3)$，常数小。
其思想是动态规划。