最短路（迪杰斯特拉/贝尔曼/SPFA）
-
- dijiesitela
-
-
- bellman
-
- SPFA
- 堆优化Dijkstra
dijiesitela
（时间复杂度（N×N），求单点到其他所有点之间的最短路）
// #include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f
int map[1550][1550], vis[1550],dis[1550];//dis[i]是X点到I点的最短路//vis[i]标记此点有没有被当做过中间点
int main()
{
int i, j, n, m, a, b,flag,min,c,x;
scanf("%d %d %d",&m, &n, &x);//有N个点，M条点之间的信息，求X点到其他点之间的最短路
//对点之间的距离初始化
for(i = 1; i <= n; i ++)
{
for(j = 1; j <= n; j ++)
{
if(i == j)
map[i][j] = 0;
else
map[i][j] = inf;
}
}
//输入点之间的距离信息
for(i = 0; i < m; i ++)
{
scanf("%d %d %d",&a, &b, &c);
if(map[a][b] > c)
map[a][b] = map[b][a] = c;
}
for(i = 1; i <= n; i ++)//对dis[], vis[],初始化
{
dis[i] = map[x][i];
vis[i] = 0;
}
vis[x] = 1;//x点不能当做中间点
for(i = 0; i < n; i ++)//因为vis[x]已经是1，所以循环进行n-1次
{
min = inf;
for(j = 1; j <= n; j ++)//此循环寻找一个距离x点距离最小的点flag
{
if(vis[j] == 0&&dis[j] < min)
{
min = dis[j];
flag = j;
}
}
vis[flag] = 1;//标记flag点
for(j = 1; j <= n; j ++)//通过flag对路径进行压缩
{
if(dis[j] > dis[flag] + map[flag][j])
dis[j] = dis[flag] + map[flag][j];
}
}
for(i = 1; i <= n; i ++)//输出x点到所有点之间的最短距离
{
if(i == n)
printf("%d\n",dis[n]);
else
printf("%d ",dis[n]);
}
return 0;
}
下面两种算法解这题：http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2718/pid/3363
bellman
（比djstl复杂度高O（M× N）（点×边），但可以判断是否存在负权，求单点到其他所有点之间的最短路）
// #include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int start, end, length,price;
}rode[250000];
int len[600], pri[600],m,n,flag,head;
void add(int a, int b, int c, int d)
{
rode[++head].start = a;
rode[head].end = b;
rode[head].length = c;
rode[head].price = d;
}
void bellman(int s, int e)
{
int i, j;
memset(len,0x3f3f3f3f,sizeof(len));
memset(pri,0x3f3f3f3f,sizeof(pri));
len[s] = 0;
pri[s] = 0;
for(i = 1;i <= n-1;i ++)//对每条边进行第一遍松弛操作的时候，生成了从s出发，层数为1的最短路。也就是找到了从s出发，经过1条边到达其他点的最短路,对每条边进行第二次松弛操作时，生成了从s出发，层数为2的的最短路，也就是从s出发，经过2条边到达其他点的最短路，以此类推。因为最短路最多含有n-1条边，所以最多进行n-1次松弛操作。
{
flag = 1;
for(j = 0;j <= head;j ++)
{
if(len[rode[j].end] > len[rode[j].start] + rode[j].length||(len[rode[j].end] == len[rode[j].start] + rode[j].length&&pri[rode[j].end] > pri[rode[j].start] +rode[j].price))//如果S点到len[rode[j].end的距离，可以通过中间点len[rode[j].start]缩短，那么更新这个值
{
len[rode[j].end] = len[rode[j].start] + rode[j].length;
pri[rode[j].end] = pri[rode[j].start] +rode[j].price;
flag = 0;
}
}
if(flag)
break;
}
/*for(j = 0;j <= head;j ++)
{
if(len[rode[j].end] > len[rode[j].start] + rode[j].length||
//若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成
}
}*/
printf("%d %d\n",len[e],pri[e]);
}
int main()
{
int i, s,e,t,a,b,c,d;
scanf("%d",&t);
while(t --)
{
scanf("%d %d %d %d",&n, &m, &s,&e);
head = -1;
for(i = 0;i < m;i ++)
{
scanf("%d %d %d %d",&a, &b,&c,&d);
add(a,b,c,d);
add(b,a,c,d);
}
bellman(s,e);
}
}
SPFA
(bellman的队列优化，链式前向星)
链式前向星的讲解：https://blog.csdn.net/ACdreamers/article/details/16902023
把初始点放进队列，每次取出队首结点u，并且用u点当前的最短路径估计值对u点一步可达的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾，这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
// #include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
int w,p,to,next;//长度，价格，边的终点，与此边同起点的下一条边在edge中的位置
} edge[12000];
int head[12000],cnt;//从每个点出发的（输入的）最后一条边的位置,
int dis[12000],pri[12000],flag[12000],num[12000];//每个点到起始点的最短路,每个点到起始点的最少钱，每个点当前有（1）没有（0）被放进队列,每个点被放进了队列多少次
void add(int u, int v, int w,int p)
{
edge[cnt].w = w;//长度
edge[cnt].p = p;//价格
edge[cnt].to = v;//次边终点
edge[cnt].next = head[u];//head[u]为与此边同起点的的（输入的）上一条边在edge中的位置（或无，为-1）
head[u] = cnt++;//起点为u的边的（输入的）最后一条边更新为当前输入的这条边
}
void spfa(int s,int e,int n)
{
int x,i,y;
queue <int> q;
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(pri,0x3f3f3f3f,sizeof(pri));
memset(flag,0,sizeof(flag));
memset(num,0,sizeof(num));
dis[s] = 0;
pri[s] = 0;//初始化
q.push(s);//先把起始点放进队列
flag[s] = 1;
num[s] ++;
while(!q.empty())
{
x = q.front();
q.pop();//取出队头的点
flag[x] = 0;
for(i = head[x]; i>= 0; i = edge[i].next)//对于取出来的队头的点（x），遍历其所有一步可到达的点
{
y = edge[i].to;//此点为y
if(dis[y] > dis[x] + edge[i].w||(dis[y] == dis[x] + edge[i].w&&pri[y] > pri[x] + edge[i].p))//与bellman一样，w优先最小，其次是p
{
dis[y] = dis[x] + edge[i].w;
pri[y] = pri[x] + edge[i].p;
if(!flag[y])//如果y点的最短路被更新了,而且y点没有在队列里
{
q.push(y);//把它放进队列
num[y]++;
flag[y] = 1;
// if(num[y] > n)//如果一个点被放进了队列超过了n次，还能松弛，那么他就一定存在负环，返回
// return false;
}
}
}
}
printf("%d %d\n",dis[e],pri[e]);//最短路，最短路下的最少钱
//return true;
}
int main()
{
int i,m,n,s,t,a1,a2,a3,a4,e;
scanf("%d",&t);
while(t --)
{
scanf("%d %d %d %d",&n, &m, &s, &e);//n个点，m条边，计算s到e点的最短路,无向图
cnt = 0;//第cnt次输入
memset(head,-1,sizeof(head));//把head都赋值为-1，表以i点为起点的的（输入的）最后一条边的储存位置不存在
for(i = 0; i < m; i ++)
{
scanf("%d %d %d %d",&a1, &a2,&a3,&a4);//从a1到a2有一条，长度a3，价格a4的无向边
add(a1,a2,a3,a4);//无向图
add(a2,a1,a3,a4);
}
spfa(s,e,n);//出发点，目的地,n个点
}
return 0;
}
堆优化Dijkstra
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e6+5;
struct node
{
int to,next,dis;
} edge[maxn<<1];
int head[maxn<<1],cnt,vis[maxn],dis[maxn];
void add(int u,int v,int dis)
{
edge[cnt].to = v;
edge[cnt].next =head[u];
edge[cnt].dis =dis;
head[u] = cnt++;
}
int dijkstra(int s,int t)
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > >que;
dis[s] = 0;
que.push(make_pair(0,s));
while(!que.empty())
{
pair<int,int>p = que.top();
que.pop();
if(vis[p.second])
continue;
vis[p.second] = 1;
for(int i = head[p.second];i!=-1;i = edge[i].next)
{
int to = edge[i].to;
if(!vis[to]&&dis[to]>dis[p.second]+edge[i].dis)
{
dis[to] = dis[p.second]+edge[i].dis;
que.push(make_pair(dis[to],to));
}
}
}
return dis[t];
}
int main()
{
int i,j,m,n,u,v,w,s,t;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));
cnt = 0;
for(i = 0; i<m; i++)
{
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
scanf("%d %d",&s,&t);
printf("%d\n",dijkstra(s,t));
}
return 0;
}
![2017年团体程序设计天梯赛-决赛小结[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)