Dijkstra
目录
- 《算法笔记》重点摘要
- 1003 Emergency (25)
《算法笔记》 10.4.1 Dijkstra 重点摘要
对任意给出的图 G(V,E) 和 起点 S，终点 T，求 S 到 T 的最短路径
1. 简介
- 解决单源最短路问题
- 只能处理所有边权均非负的情况
2. 邻接矩阵
const int MAXV = 1000;
const int INF = 0x3fffffff;
int n, G[MAXV][MAXV], d[MAXV], pre[MAXV];
bool vis[MAXV] = {false};
void Dijkstra(int s){
fill(d, d + MAXV, INF);
d[s] = 0;
for (int i = 0; i < n; i++) pre[i] = i;
for (int i = 0; i < n; i++){
int u = -1, MIN = INF;
for (int j = 0; j < n; j++){ // 找未访问结点中 d[] 最小的
if (!vis[j] && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if (u == -1) return; // 找不到 d[u] < INF 点，说明剩下的点与起点 s 不连通
vis[u] = true;
for (int v = 0; v < n; v++){
if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
pre[v] = u;
}
}
}
}
void DFS(int s, intv){
if (v == s){
printf("%d", s);
return;
}
DFS(s,pre[v]);
printf(" %d", v);
}
3. 第二标尺
(1) 新增边权
int cost[MAXV][MAXV], c[MAXV];
fill(c, c + MAXV, INF);
c[s] = 0;
for (int v = 0; v < n; v++){
if (!vis[v] && G[u][v] != INF){
if (d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]){
pre[v] = u;
c[v] = c[u] + cost[u][v];
}
else if (d[u] + G[u][v] < d[v]){
pre[v] = u;
d[v] = d[u] + G[u][v];
c[v] = c[u] + cost[u][v];
}
}
}
(2) 新增点权
int weight[MAXV], w[MAXV] = {0};
w[s] = weight[s];
for (int v = 0; v < n; v++){
if (!vis[v] && G[u][v] != INF){
if (d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v]){
pre[v] = u;
w[v] = w[u] + weight[v];
}
else if (d[u] + G[u][v] < d[v]){
pre[v] = u;
d[v] = d[u] + G[u][v];
w[v] = w[u] + weight[v];
}
}
}
(3) 求最短路径条数
int num[MAXV] = {0};
num[s] = 1;
for (int v = 0; v < n; v++){
if (!vis[v] && G[u][v] != INF){
if (d[u] + G[u][v] == d[v]{
pre[v] = u;
num[v] += num[u];
}
else if (d[u] + G[u][v] < d[v]){
pre[v] = u;
d[v] = d[u] + G[u][v];
num[v] = num[u];
}
}
}
1003 Emergency (25)
题目思路
- 两个标尺：距离，点权；且要求最短路径数
#include<iostream>
using namespace std;
const int MAXN = 500, INF = 0x3fffffff;
int n, s, t, G[MAXN][MAXN], weight[MAXN], d[MAXN], pathnum[MAXN], w[MAXN] = {0};
bool vis[MAXN] = {false};
void Dijkstra(){
fill(d, d + MAXN, INF);
d[s] = 0;
pathnum[s] = 1;
w[s] = weight[s];
for (int i = 0; i < n; i++){
int u = -1, MIN = INF;
for (int j = 0; j < n; j++){
if (!vis[j] && d[j] < MIN){
u = j;
MIN = d[j];
}
}
vis[u] = true;
for (int v = 0; v < n; v++){
if (!vis[v] && G[u][v] != INF){
if (d[v] == d[u] + G[u][v]){
pathnum[v] += pathnum[u];
if (w[v] < w[u] + weight[v]) w[v] = w[u] + weight[v];
}
else if (d[v] > d[u] + G[u][v]){
d[v] = d[u] + G[u][v];
w[v] = w[u] + weight[v];
pathnum[v] = pathnum[u];
}
}
}
}
}
int main()
{
int m, u, v, len;
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 0; i < n; i++) scanf("%d", &weight[i]);
fill(G[0], G[0] + MAXN * MAXN, INF);
for (int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &len);
G[u][v] = len;
G[v][u] = len;
}
Dijkstra();
printf("%d %d", pathnum[t], w[t]);
return 0;
}
fill(G[0], G[0] + MAXN * MAXN, INF)注意二维数组要取首地址作为指针类型不能直接用数组名，因为它相当于是一维数组的指针，而参数要求是指针