我们有一条u->v的边，s是我们的起点。那么如果. S->V可以通过s->u,u->v来缩短距离那么就更新。我们称之为【松弛】
我们可以每次对图中每条边u->v都拿出起点，松弛。直到每一次操作都不会改变dist数组的时候。Dist数组就是答案。（可以证明这样最多我们只要进行n-1次操作，每次操作拿出全部的m条边松弛，复杂度O(n*m)，这就是bellman ford）。
但是，起点附近的松弛必定会影响其他点，起点没松弛完，终点附近的变的松弛可以说是无效的。简单来说，近的点的dist还没确定，就用这个未确定的dist取更新远的点，浪费时间。
所以我们需要一个队列优化。
在队列中的点，需要松弛。我们先把起点丢进队列。具体看代码。
Dist数组记录距离，inq数组标记是否在队列
int SPFA(int s, int t) {
int dist[maxn], inq[maxn];
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, inq[i] = 0;
}
queue<int>que;
que.push(s), inq[s] = 1, dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
inq[now] = 0;
for(int i = first[now]; ~i; i = edge[i].next) { //每次拿出一个点开始松弛。
int to = edge[i].to, w = edge[i].w;
if(dist[to] > dist[now] + w) { //这个if看下面的图
dist[to] = dist[now] + w;
if(!inq[to]) { //松弛过的点dist变换了，可能影响其他的点。需要继续松弛
inq[to] = 1;
que.push(to);
}
}
}
}
return dist[t] == inf ? -1 : dist[t];
}
平常我们写结构体这么写
struct Point {
int x, y;
};
Point a; //c++才能这么写，c语言中要struct Point a;或者typedef后才能直接point a;
这是结构体a的值不确定。
struct Point {
int x, y;
Point() {}
};
其实它默认有一个没有返回值，和结构体同名的函数，什么都不干。如果我们给他加点东西
struct Point {
int x, y;
Point() { x = 0; y = 0};
};
这样Point a;那么a.x和a.y都是0.
如果我们这么写
struct Point {
int x, y;
Point() { x = 0; y = 0};
Point(int xx, int yy) {
X = xx;
Y = yy;
}
};
那么Point a(2, 3), 点a的x就是2，y就是3。
所以 queue<Point >que; que.push(Point(2, 3));能直接往队列丢一个(2,3)的结构体
Floyd代码#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
int n, m, mp[maxn][maxn];
void init() {
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < n; j ++ ) {
if(i == j) {
mp[i][j] = 0;
} else {
mp[i][j] = inf;
}
}
}
}
int main() {
int u, v, w;
while(~scanf("%d %d", &n, &m)) {
init();
for(int i = 1; i <= m; i ++ ) {
scanf("%d %d %d", &u, &v, &w);
mp[u][v] = mp[v][u] = min(mp[u][v], w);
}
for(int k = 0; k < n; k ++ ) {
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < n; j ++ ) {
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
}
int s, t;
scanf("%d %d", &s, &t);
printf("%d\n", mp[s][t] == inf ? -1 : mp[s][t]);
}
return 0;
}
Dijkstra O(n^2),链式前向星
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
int n, m, first[maxn], sign;
struct Edge {
int to, w, next;
} edge[maxn * 2];
void init() {
for(int i = 0; i < n; i ++ ) {
first[i] = -1;
}
sign = 0;
}
void add_edge(int u, int v, int w) {
edge[sign].to = v;
edge[sign].w = w;
edge[sign].next = first[u];
first[u] = sign ++;
}
int dist[maxn], vis[maxn];
int dijkstra(int s, int t) {
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, vis[i] = 0;
}
dist[s] = 0;
for(int k = 1; k <= n; k ++ ) { ///dist数组n个，每次确定一个值
vis[s] = 1;
for(int i = first[s]; ~i; i = edge[i].next) { ///更新dist数组
int to = edge[i].to, w = edge[i].w;
if(!vis[to] && dist[to] > dist[s] + w) {
dist[to] = dist[s] + w;
}
}
int mincost = inf;
for(int i = 0; i < n; i ++ ) { ///找最小
if(!vis[i] && dist[i] < mincost) {
mincost = dist[i];
s = i;
}
}
}
if(dist[t] == inf) {
return -1;
} else {
return dist[t];
}
}
int main() {
int u, v, w;
while(~scanf("%d %d", &n, &m)) {
init();
for(int i = 1; i <= m; i ++ ) {
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
int s, t;
scanf("%d %d", &s, &t);
printf("%d\n", dijkstra(s, t));
}
return 0;
}
Dijkstra + priority_queue + 链式前向星
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
int n, m, first[maxn], sign;
struct Edge {
int to, w, next;
} edge[maxn * 2];
void init() {
for(int i = 0; i < n; i ++ ) {
first[i] = -1;
}
sign = 0;
}
void add_edge(int u, int v, int w) {
edge[sign].to = v;
edge[sign].w = w;
edge[sign].next = first[u];
first[u] = sign ++;
}
struct Node {
int to, cost;
Node() {}
Node(int tt, int cc):to(tt), cost(cc) {}
friend bool operator < (const Node &a, const Node &b) {
return a.cost > b.cost;
}
};
int dist[maxn], vis[maxn];
int dijkstra(int s, int t) {
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, vis[i] = 0;
}
priority_queue<Node>que;
que.push(Node(s, 0));
while(!que.empty()) {
Node now = que.top();
que.pop();
if(!vis[now.to]) {
vis[now.to] = 1;
dist[now.to] = now.cost;
for(int i = first[now.to]; ~i; i = edge[i].next) {
int to = edge[i].to, w = edge[i].w;
if(!vis[to]) {
que.push(Node(to, now.cost + w));
}
}
}
}
if(dist[t] == inf) {
return -1;
} else {
return dist[t];
}
}
int main() {
int u, v, w;
while(~scanf("%d %d", &n, &m)) {
init();
for(int i = 1; i <= m; i ++ ) {
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
int s, t;
scanf("%d %d", &s, &t);
printf("%d\n", dijkstra(s, t));
}
return 0;
}
SPFA链式前向星
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 205;
const int maxm = 1005;
const int inf = 0x3f3f3f3f;
int n, m, first[maxn], sign;
struct Edge {
int to, w, next;
} edge[maxn * maxn];
void init() {
for(int i = 0; i < n; i ++ ) {
first[i] = -1;
}
sign = 0;
}
void add_edge(int u, int v, int w) {
edge[sign].to = v;
edge[sign].w = w;
edge[sign].next = first[u];
first[u] = sign ++;
}
int SPFA(int s, int t) {
int dist[maxn], inq[maxn];
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, inq[i] = 0;
}
queue<int>que;
que.push(s), inq[s] = 1, dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
inq[now] = 0;
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, w = edge[i].w;
if(dist[to] > dist[now] + w) {
dist[to] = dist[now] + w;
if(!inq[to]) {
inq[to] = 1;
que.push(to);
}
}
}
}
return dist[t] == inf ? -1 : dist[t];
}
int main()
{
while(~scanf("%d %d", &n, &m)) {
init();
for(int i = 1; i <= m; i ++ ) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
int s, t;
scanf("%d %d", &s, &t);
printf("%d\n", SPFA(s, t));