题目训练链接（密码hpuacm）： https://vjudge.net/contest/246705
我会分别用 迪杰斯特拉 优先队列和链式前向星优化过的迪杰斯特拉 SPFA算法 三种方法讲一下例题。
此外上述三种算法是求单源最短路问题， 这里还会介绍一下多源最短路的算法 floyd算法。多源最短路可以求出任意两点间的最短距离。
在存图方式中会用到邻接矩阵 链式前向星等存图方式，不知道的可以先了解一下
邻接矩阵存图 点这里！！！
链式前向星 点这里！！！
再介绍一位牛人的博客 点这里！！！
提示： 二维矩阵或者一般用来点非常多边也非常多的图，就是稠密图，vector存图是点和边都比较少的图，存的是稀疏图，
链式前向星存图则限制条件比较小，链式前向星其实存的是边。
上文的链式前向星的，博主没有给出具体代码。我这里给出
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
struct Edge{
int to, val, next;
// edge[i].to表示第i条边的终点,
//edge[i].next表示与第i条边同起点的下一条边的存储位置,
//edge[i].w为边权值
};
struct Edge edge[MAXN];
int head[MAXN]; // 表示以i为起点的最后一条边存储的位置
int cnt = 0;
void add( int u, int v, int val )
{
edge[cnt].to = v;
edge[cnt].val = val;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int main()
{
memset(head, -1, sizeof(head));
cnt = 0;
int n;
int a, b, c;
scanf("%d", &n);
for( int i=0; i<n; i++ )
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int p;
scanf("%d", &p);
printf("u v val\n");
for( int i=head[p]; i != -1; i = edge[i].next )
{
printf("%d %d %d\n", p, edge[i].to, edge[i].val);
}
return 0;
}
来道题理解一下，给出的代码可以作为模板使用
Til the Cows Come Home
Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.
Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.
Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
Input
* Line 1: Two integers: T and N
* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.
Output
* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.
Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100 Sample Output
90 Hint
INPUT DETAILS:
There are five landmarks.
OUTPUT DETAILS:
Bessie can get home by following trails 4, 3, 2, and 1.
题目大意就是一头牛从第N个路标到第一个路标，问最短距离是多少？
第一种方法： 迪杰斯特拉算法
// <2> djk求单源最短路,邻接矩阵存图 时间复杂度o(n^2)
//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXN = (int) 1000+7;
const int INF = (int) 0x3f3f3f3f;
int n, m; // n个点 m条边
int mp[MAXN][MAXN];
void init( int n ) // 初始化
{
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=n; j++ )
{
if( i == j )
mp[i][j] = 0;
else
mp[i][j] = mp[j][i] = INF;
}
}
}
void getmap( int m ) // 建图
{
int u, v, val; // u 到 v 有一条权值为val的边
while( m-- )
{
scanf("%d%d%d", &u, &v, &val);
mp[u][v] = mp[v][u] = min(mp[u][v], val); //双向边，且防止有重边
}
}
bool vis[MAXN]; // 标记是否走过
int dis[MAXN]; // 起点到其他点的距离
void djk( int st, int ed )
{
for( int i=1; i<=n; i++ ) // 初始化vis and dis
{
vis[i] = 0;
dis[i] = mp[st][i]; // 初始所有dis都是起点到任一点的距离
}
vis[st] = 1;
for( int i=2; i<=n; i++ ) // 只是循环 n-1 遍
{
int minum = INF, id = -1;
for( int j = 1; j<=n; j++ )
{
if( !vis[j] && dis[j] < minum )
minum = dis[j], id = j;
}
if( id == -1 ) break; // 没找到
vis[id] = 1;
for( int j=1; j<=n; j++ ) // 这个循环会更新，所有 起点通过距离他最短
{ // 的点到下一个点和它同时可以直接到达这个
if( !vis[j] && mp[id][j] != INF ) // 点的距离，取两种路径的最小值
{ // 可以把已经找到最短路上的点看做一个集合
if( dis[j] > dis[id] + mp[id][j] ) // 新的距离这个集合最短的
dis[j] = dis[id] + mp[id][j]; // 点看做中转点，集合，中转点
} // 下一个未访问过的点三者构成一个三角形
}
}
printf("%d\n", dis[ed]);
}
int main()
{
int t;
scanf("%d%d", &t, &n);
init(n);
getmap(t);
djk(n, 1);
return 0;
}
第二种方法： 优先队列和链式前向星优化过的迪杰斯特拉
// <3> 优先队列优化的djk求单源最短路,链式前向星存图 时间复杂度o(E * log(V))
//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e5 + 7;
const int INF = (int) 0x3f3f3f3f;
typedef pair<int, int> Pair;
struct Edge
{
int to, val, next; // 成员变量， struct 默认public
Edge(){}; // 构造函数
Edge( int _to, int _val, int _next )
{
to = _to; val = _val; next = _next;
}
};
struct Edge edge[MAXN << 1]; // 乘2
int n, m; // n 是图中的点数，m是图中的边数
int head[MAXN]; // head[i] 表示以i为起点最后一条边的存储位置
int cnt; // 第cnt次输入
void init( int n ) // 初始化
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void add( int u, int v, int val ) // 链式前向星加边函数, 加单向边
{
edge[cnt] = Edge(v, val, head[u]);
head[u] = cnt++;
}
void getmap( int m ) // 建图
{
int u, v, val;
while( m-- )
{
scanf("%d%d%d", &u, &v, &val);
add(u, v, val);
add(v, u, val); // 如果是双向图，加上这一行
}
}
int dis[MAXN]; // 距离
void djk( int st, int ed )
{
memset(dis, 0x3f, sizeof(dis));
priority_queue< Pair, vector<Pair>, greater<Pair> > q; // 升序排列，但先取出的是较小的
dis[st] = 0;
q.push(make_pair(0, st)); // 第一个值是当前点到起点的距离
while( !q.empty() )
{
Pair p = q.top(); // 每次取离起点最近的
q.pop();
int v = p.second;
if( dis[v] < p.first ) continue;
for( int i=head[v]; i != -1; i = edge[i].next ) // 链式前向星存图方式的遍历
{
Edge e = edge[i];
if( dis[e.to] > dis[v] + e.val )
{
dis[e.to] = dis[v] + e.val;
q.push(make_pair(dis[e.to], e.to));
}
}
}
printf("%d\n", dis[ed] == INF ? -1 : dis[ed]);
}
int main()
{
int t;
scanf("%d%d", &t, &n);
init(n);
getmap(t);
djk(n, 1);
return 0;
}
第三种方法： SPFA算法
// <1> spfa求单源最短路,链式前向星存图 时间复杂度o(kE) k是常数，大多数情况下为2
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = (int) 1e5+11;
const int INF = (int) 0x3f3f3f3f;
struct Edge{
int to, val, next;
Edge(){}
Edge( int _to, int _val, int _next )
{
to = _to; val = _val; next = _next;
}
};
struct Edge edge[MAXN << 1];
int n, m; // n 是图中的点数，m是图中的边数
int head[MAXN], cnt;
void init( int n )
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void add( int u, int v, int val )
{
edge[cnt] = Edge(v, val, head[u]);
head[u] = cnt++;
}
void getmap( int m )
{
int u, v, val;
while( m-- )
{
scanf("%d%d%d", &u, &v, &val); // u->v有边
add(u, v, val);
add(v, u, val); // 如果是双向图，加上这个代码
}
}
bool vis[MAXN];
int dis[MAXN];
void spfa( int st, int ed )
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(st);
vis[st] = 1; // 标记走过了
dis[st] = 0; // 起点到自身的距离为0
while( !q.empty() )
{
int u = q.front();
q.pop();
vis[u] = 0;
for( int i=head[u]; ~i; i = edge[i].next )
{
Edge e = edge[i];
if( dis[e.to] > dis[u] + e.val )
{
dis[e.to] = dis[u] + e.val;
if( !vis[e.to] ) // 访问过的点不在放入队列
{
q.push(e.to);
vis[e.to] = 1; // 标记走过了
}
}
}
}
printf("%d\n", dis[ed] == INF ? -1 : dis[ed]); // st到不了ed输出-1
}
int main()
{
int t;
scanf("%d%d", &t, &n);
init(n);
getmap(t);
spfa(n, 1);
return 0;
}
第四种方法： floyd算法
// <4> floyd求多源最短路,邻接矩阵存图 时间复杂度o(n^3)，可求得任意两个点之间的最短距离
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = 1000+7;
const int INF = 0x3f3f3f3f;
int n, m;
int mp[MAXN][MAXN];
void init(int n) // 初始化
{
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=n; j++ )
{
if( i == j )
mp[i][j] = 0;
else
mp[i][j] = mp[j][i] = INF;
}
}
}
void getmap( int m ) // 建图
{
int u, v, val;
while( m-- )
{
scanf("%d%d%d", &u, &v, &val);
mp[u][v] = mp[v][u] = min(mp[u][v], val); // 双向图写这行
//mp[u][v] = min(mp[u][v], val); // 单向图写着行
}
}
void floyd( int n )
{
for( int k=1; k<=n; k++ ) // k为三角形模型的中间点
{
for( int i=1; i<=n; i++ )
{
for( int j=1; j<=n; j++ )
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]); // dp
}
}
}
int main()
{
int t;
scanf("%d%d", &t, &n);
init(n);
getmap(t);
floyd(n);
printf("%d\n", mp[n][1] == INF ? -1 : mp[n][1]);
return 0;
}
京公网安备 11010502036488号