一、适用条件
单源最短路问题、非负权图
二、算法思想
三、朴素的dijkstra（邻接矩阵存图）
时间复杂度分析
O（v*v）, 顶点的二次方
题目来源：https://www.acwing.com/problem/content/851/
- Dijkstra求最短路 I
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
【输入格式】
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
【输出格式】
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
【数据范围】
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
【输入样例】：
3 3
1 2 2
2 3 1
1 3 4
【输出样例】：
3
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int INF = 0x3f3f3f;
int g[maxn][maxn], d[maxn];
bool vis[maxn];
void init(int n){
for(int i=1; i<=n; i++) // 初始化全部为不相连
for(int j=1; j<=n; j++)
g[i][j] = INF;
for(int i=1; i<=n; i++){
d[i] = INF; // 最短距离初始化
g[i][i] = 0; // 防止有自环
vis[i] = false; // 标记点还未确定最短距离
}
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
init(n);
for(int i=1; i<=m; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
g[x][y] = min(g[x][y], z); //重边的话，选较小的权值
}
d[1] = 0; // 起点，此处是顶点1
for(int i=1; i<=n; i++){
int u, minx = INF; // u是距离起点最近的点
for(int j=1; j<=n; j++)
if(!vis[j] && d[j]<minx){
minx = d[j];
u = j;
}
vis[u] = true;
for(int j=1; j<=n; j++) // 松弛
d[j] = min(d[j], d[u]+g[u][j]); // d[j]相当于g[1][j]
}
if(d[n]==INF) // n是终点，判断是否连通
printf("-1");
else
printf("%d", d[n]);
return 0;
}
四、堆优化的dijkstra(邻接表存图)
题目来源：https://www.acwing.com/problem/content/852/
- Dijkstra求最短路 II
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
【输入格式】
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
【输出格式】
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
【数据范围】
1≤n,m≤105,
图中涉及边长均不超过10000。
【输入样例】：
3 3
1 2 2
2 3 1
1 3 4
【输出样例】：
3
与上一题，区别是n与m的区别，此处是稀疏图，上一题是稠密图。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int INF = 0x3f3f3f;
struct edge{
int from, to, cost;
};
vector<edge> G[maxn];
typedef pair<int, int> P; // first是距离，second是顶点，pair排序默认是先first，再是second
int d[maxn], n;
void dijkstra(int s, int t){
priority_queue<P, vector<P>, greater<P> > Q; // 小根堆
for(int i=1; i<=n; i++)
d[i] = INF;
d[s] = 0;
Q.push(P(0, s));
while(!Q.empty()){
P u = Q.top();
Q.pop();
int v = u.second; // 顶点
if(d[v]<u.first) // 已经处理过了
continue;
for(int i=0; i<G[v].size(); i++){ //松弛
edge e = G[v][i];
if(d[e.to]>d[v]+e.cost) {
d[e.to] = d[v]+e.cost;
Q.push(P(d[e.to], e.to)); // 更新后的结点信息
}
}
}
cout << d[t];
}
int main(){
int m, x, y, z;
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> x >> y >> z;
G[x].push_back((edge){x, y, z});
}
dijkstra(1, n);
return 0;
}
