最短路问题
内容：给定两个顶点，在以这两个点为起点和终点的路径中，边的权值和最小的路径。如果把权值当作距离，考虑最短距离的话就很容易理解了。
最短路的例子
单源最短路问题1（Bellman-Ford算法）
单源最短路问题是固定一个起点，求它到其他所有点的最短路的问题。终点也固定的问题叫做两点之间最短路问题。但是因为解决单源最短路问题的复杂度也是一样的，因此通常当作单源最短路问题来求解
记从起点s出发到顶点i的最短距离为d[i]，则下述等式成立。
d[i]=min{d[j]+(从j到i的边的权值)|e=(j,i)∈E}
如果给定的图是一个DAG（有向无环图）就可以按拓扑序给定点编号，并利用用这条递推关系式计算出d。但是，如果图中有圈，就无法以来这样的顺序进行计算。在这种情况下，记当前到顶点i的最短路长度为d[i]，并设初值d[s]=0,d[i]=INF(足够大的常数)，再不断使用这条递推关系式更新d的值，就可以算出新的d。只要图中不存在负圈，这样的更新操作就是有限的。结束之后的d就是所求的最短距离了。
模板
//从顶点from指向顶点to的权值为cost的边
struct edge{
int from,to,cost;
};
edge es[MAX_E];//边
int d[MAX_V];//最短距离
int V,E;//V是顶点数，E是变数
//求解从顶点s出发到所有点的最短距离
void shortest_path(int s){
for(int i=0;i<V;i++)
d[i]=INF;
d[s]=0;
while(true){
bool updata=false;
for(int i=0;i<E;i++){
edge e=es[i];
if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
update=true;
}
}
if(!update)
break;
}
}
这个算法叫做Bellman-Ford算法。如果在图中不存在从s可达的负圈，那么最短路不会经过同一个顶点两次（也就是说，最多通过|V|-1条边），while（true）的循环也最多执行|V|-1次，因此，复杂度是O（|V|*|E|）。反之，如果存在从s可达的负圈，那么在第|V|次循环中也会更新d的值，因此也可以用这个性质来检查负圈。如果一开始对所有的顶点i，都把d[i]初始化为0，那么可以检查出所有的负圈。
//如果返回true则存在负圈
bool find_negative_loop(){
memset(d,0,sizeof(d));
for(int i=0;i<V;i++){
for(int j=0;j<E;j++){
edge e=es[j];
if(d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
//如果第n次仍然更新了，则存在负圈
if(i==V-1)
return true;
}
}
}
return false;
}
单源最短路问题2（Dijkstra算法）//迪杰克斯拉
让我们考虑没有负边的情况。在Bellman-Ford算法中，如果d[i]还不是最短距离的话，那么即使进行d[j]=d[i]+(从i到j的边的权值的更新)，d[j]也不会变成最短距离。而且䩚d[i]没有变化，每一次循环也要检查一遍从i出发的所有边。这显然是很浪费时间的。因此可以对算法做如下修改。
- 找到最短距离和已经确定的顶点，从它出发更新相邻顶点的最短距离。
-
此后不需要再关心1中的“最短距离已经确定的顶点”
上面提到的“最短距离已经确定的顶点”要怎么得到是问题的关键。在最开始时，只有起点和最短距离是确定的。而在尚未使用过的顶点中，距离d[i]最小的顶点就是最短距离已经确定的顶点。这是因为由于不存在负边，所以d[i]不会在之后的更新中变小。这个算法叫做Dijkstra算法。
int cost[MAX_V][MAX_V];//cost[u][v]表示边e=（u，v）的权值（不存在边是设为INF）
int d[MAX_V];//顶点s出发的最短距离
bool used[MAX_V];//已经使用过的图
int V;//顶点数
//求从起点s出发到各个顶点的最短距离
void dijkstra(int s){
fill(d,d+V,INF);
fill(used,used+V,false);
d[s]=0;
while(true){
int v=-1;
//从尚未使用过的顶点中选择一个距离最小的顶点
for(int u=0;u<V;u++){
if(!used[u]&&(v==-1||d[u]<d[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;
for(int u=0;u<V;u++){
d[u]=min(d[u],d[v]+cost[v][u]);
}
}
}
使用邻接矩阵实现的Dijkstra算法的复杂度是O(|V|2)。使用邻接表的话，更新最短距离只需要访问每一条边即可，因此最终复杂度还是O(|V|2)。在|E|比较小时，大部分的时间花在了查找下一个使用的顶点上，因此需要使用合适的数据结构对其进行优化。
需要优化的是数值插入（更新）和取出最小值的两个操作，因此使用堆就可以了。把每个顶点当前的最短距离用堆维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质，而每次从堆中取出的最小值就是下一次要使用的顶点。这样堆中元素共有O（|V|）个，更新和取出数值的操作有O（|E|）次，因此整个算法的复杂度是O（|E|log|V|）
下面是使用STL的priority_queue实现。在每次更新时网堆里插入当前最短距离和顶点的值对。插入的次数是O（|E|）次，因此元素也是O（|E|）个。当取出的最小值不是最短距离的话，就丢弃这个值。这样整个算法也可以在同样的复杂度内完成。
struct edge{
int to,cost;
};
typedef pair<int,int> P;//first是最短距离，second是顶点的编号
int V;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s){
//通过greater<P>参数，堆参照first从小到大的顺序取出值
priority_queue<P,vector<P>,greater<P> > que;
fill(d,d+V,INF);
d[s]=0;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
id(d[v]<p.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;
que.push(P(d[e.to],e.to));
}
}
}
}
任意两点间的最短路问题（Floyd-Warshall算法）
求解所有两点间的最短路问题叫做任意两点间的最短路问题。让我们试着用DP求解任意两点间的最短路问题。只是用顶点
0 ~ k和i，j的情况下，记i到j的最短路长度为d[k+1][i][j]，当k=-1时，认为只使用i和j，所以d[0][i][j]=cost[i][j]。接下来让我们把只使用顶点0k的问题归约到只使用0k-1 的问题上。
只使用0~k时，我们分i到j的最短路正好经过顶点k一次和完全不经过顶点k两种情况来讨论。不经过顶点k的情况下，d[k][i][j]=d[k-1][i][j]。通过顶点k的情况下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。合起来就得到了d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])这个DP也可以使用同一个数组，不断进行d[i][j]=min(d[i][j],d[i][k]+d[k][j])的更新来实现。
这个算法叫做Floyed-Warshall算法，可以在O（|V^3|）时间里求得所有两点间的最短路长度。Floyd-Warshall算法和Bellman-Ford算法一样，可以处理边时负数的情况。而判断图中是否有负圈，只需要检查是否存在d[i][i]是负数的顶点i就可以了。
int d[MAX_V][MAX_V];//d[u][v]表示边e=(u,v)的权值（不存在时设为INF,不过d[i][i]=0）
int V;//顶点数
void warshall_floyd(){
for(int k=0;k<V;k++)
for(int i=0;i<V;i++)
for(int j=0;j<V;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
这样通过三重循环非常简单地就可以求出所有两点间的最短路长度。由于实现起来非常简单，如果复杂度在可以承受的范围之内，单源最短路也可以使用Floy-Warshall算法进行求解
路径还原
截至目前，我们都只是在求解最短距离。虽然许多问题只需输出最短距离就可以了，但是也有问题需要求解最短路的路径。我们以Dijkstra算法为例，试着来求解最短路径。在求解最短距离时，满足d[j]=d[k]+cost[k][j]的顶点k，就是在最短路上顶点j的前趋节点，因此通过不断寻找前趋节点就可以恢复出最短路，时间复杂度时O(|E|)。
此外，如果用prev[j]来记录最短路上顶点j的前趋，那么就可以在O（|V|）的时间内完成最短路的回复，在d[j]被d[j]=d[k]+cost[k][j]更新时，修改prev[j]=k;这样就可以求得prev数组。在计算从s出发到j的最短路时，通过prev[j]就可以知道顶点j的前趋，因此不断把j替换成prev[j]直到j=s为止就可以了。Bellman-Ford算法和Floyd-Warshall算法都可以用类似的方法进行最短路的还原。
int prev[MAX_V];//最短路上的前趋顶点
//求从起点s出发到各个顶点的最短距离
void dijkstra(int s){
fill(d,d+V,INF);
fill(used,used+V,false);
fill(prev,prev+V,-1);
d[s]=0;
while(true){
int v=-1;
for(int u=0;u<V;u++){
if(!used[u]&&(v==-1||d[u]<d[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;
for(int u=0;u<V;u++){
if(d[u]>d[v]+cost[v][u]){
d[u]=d[v]+cost[v][u];
prev[u]=v;
}
}
}
}
//到顶点t的最短路
vector<int> get_path(int t){
vector<int> path;
for(;t!=-1;t=prev[t])
path.push_back(t);//不断沿着prev[t]走直到t=s
//这样得到的就是按照t到s的顺序，所以需要翻转
reverse(path.begin(),path.end());
return path;
}
Emergency
练手题
hhh这道题笑shi我了，明明PAT AC的分数是25分，我还以为我的代码只有25分//傻了
这道题涉及的不仅仅是每条路径的值，还有每座城市都有一个权值（点权），还有相关的最短路的路径有多少条，将c1到每个城市的相同的路径计算有多少条。
#include <iostream>
#include <cstdio>
using namespace std;
const int inf=99999999;
int n,m,c1,c2;
int e[510][510],weight[510],dis[510],num[510],w[510];
bool visit[510];
void dijkstra(){
fill(visit,visit+510,false);
fill(dis,dis+510,inf);
dis[c1]=0;
w[c1]=weight[c1];
num[c1]=1;
while(true){
int v=-1;
int minn=inf;
for(int u=0;u<n;u++){
if(!visit[u]&&dis[u]<minn){
v=u;
minn=dis[u];
}
}
if(v==-1)
break;
visit[v]=true;
for(int u=0;u<n;u++){
if(!visit[u]&&e[v][u]!=inf){
if(dis[v]+e[v][u]<dis[u]){
dis[u]=dis[v]+e[v][u];
num[u]=num[v];
w[u]=w[v]+weight[u];
}else if(dis[v]+e[v][u]==dis[u]){
num[u]=num[v]+num[u];
if(w[v]+weight[u]>w[u])
w[u]=w[v]+weight[u];
}
}
}
}
printf("%d %d",num[c2],w[c2]);
}
int main()
{
//freopen("data","r",stdin);
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=0;i<n;i++)
cin>>weight[i];
fill(e[0],e[0]+510*510,inf);
int a,b,c;
for(int i=0;i<m;i++){
cin>>a>>b>>c;
e[a][b]=e[b][a]=c;
}
dijkstra();
return 0;
}
Travel Plan
路径还原
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, s, D;
int e[501][501],cost[501][501],d[501],c[501];
bool visit[501];
const int inf=99999999;
int pre[501];
void dijkstra(){
fill(d,d+501,inf);//记录e
fill(c,c+501,inf);//记录cost
fill(visit,visit+501,false);
d[s]=0;
c[s]=0;
while(true){
int v=-1;
int minn=inf;
for(int u=0;u<n;u++){
if(!visit[u]&&d[u]<minn){
minn=d[u];
v=u;
}
}
if(v==-1)
break;
visit[v]=true;
for(int u=0;u<n;u++){
if(!visit[u]&&e[v][u]!=inf){
if(d[v]+e[v][u]<d[u]){
d[u]=d[v]+e[v][u];
c[u]=c[v]+cost[v][u];
pre[u]=v;
}else if(d[u]==d[v]+e[v][u]&&c[u]>c[v]+cost[v][u]){
c[u]=c[v]+cost[v][u];
pre[u]=v;
}
}
}
}
}
void dfs(int u){
if(u==s)
return;
dfs(pre[u]);
cout<<u<<" ";
}
int main(){
// freopen("data","r",stdin);
cin>>n>>m>>s>>D;
fill(e[0],e[0]+501*501,inf);
fill(cost[0],cost[0]+501,inf);
int a,b,w,g;
for(int i=0;i<m;i++){
cin>>a>>b>>w>>g;
e[a][b]=e[b][a]=w;
cost[a][b]=cost[b][a]=g;
}
dijkstra();
cout<<s<<" ";
dfs(D);
cout<<d[D]<<" "<<c[D]<<endl;
return 0;
}
All Roads Lead to Rome
多条件
#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
#define MAX 210
int INF = 1000000;
int happy[210];
int visit[MAX];
int e[MAX][MAX];
int d[MAX];
int h[MAX];
int num[MAX];
int pre[MAX];
int count[MAX],n;
void dijkstra(int begin)
{
d[begin] = 0;
h[begin] = happy[begin];
num[begin] = 1;
count[begin] = 0;
while(true)
{
int v = -1;
int minn = INF;
for(int u = 0 ;u <n ;u++)
{
if(!visit[u] && d[u] < minn)
{
v = u;
minn= d[u];
}
}
if(v == -1) return ;
visit[v] = true;
for(int u = 0 ;u <n ;u++)
{
if(!visit[u] && e[v][u]!=INF)
{
if(d[v]+e[v][u]<d[u])
{
d[u] = d[v]+e[v][u];
num[u] = num[v];
h[u] = h[v] + happy[u];
pre[u] = v;
count[u] = count[v] +1;
}
else if(d[v]+e[v][u]==d[u])
{
num[u] = num[u] + num[v];
if(h[u] < h[v] + happy[u])
{
h[u] = h[v] + happy[u];
count[u] = count[v] +1;
pre[u] = v;
}
else if( h[u] == h[v] + happy[u] && (double)(h[v] + happy[u])/(count[v]+1) > (double)h[u]/count[u])
{
count[u] = count[v] +1;
pre[u] = v;
}
}
}
}
}
}
int main()
{
int i,j,K,Happy,ROM;
char begin[4],tem[4];
scanf("%d%d%s",&n,&K,begin);
map<string,int> mm;
map<int,string> mm2;
mm[begin] = 0;
mm2[0] = begin ;
happy[mm[begin]] = 0;
for(i = 1 ; i < n ;i++)
{
scanf("%s%d",tem,&Happy);
if(strcmp("ROM",tem)==0) ROM = i;//这里可以不要
mm[tem] = i;
mm2[i] = tem;
happy[i] = Happy;
}
char x[4],y[4];
fill(e[0],e[0]+MAX*MAX,INF);
fill(d,d+MAX,INF);
fill(h,h+MAX,INF);
fill(pre,pre+MAX,-1);
fill(count,count+MAX,0);
for(i = 0 ; i < K ;i++)
{
scanf("%s%s",x,y);
scanf("%d",&e[mm[x]][mm[y]]);
e[mm[y]][mm[x]] = e[mm[x]][mm[y]];
}
dijkstra( mm[begin]);
printf("%d %d %d %d\n",num[mm["ROM"]],d[mm["ROM"]],h[mm["ROM"]],h[mm["ROM"]]/count[mm["ROM"]]);
stack<int> ss;
i= mm["ROM"];
while(i != -1)
{
ss.push(i);
i = pre[i];
}
int fir = 1;
while(!ss.empty())
{
if(fir == 1)
{
fir = 0;
printf("%s",mm2[ss.top()].c_str());
}
else printf("->%s",mm2[ss.top()].c_str());
ss.pop();
}
printf("\n");
return 0;
}
HDU Today
STL map+Dijkstra
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define MAX 2100
int INF = 99999999,n;
int e[MAX][MAX],d[MAX];
bool visit[MAX];
map <string,int>mm;
string a,b,s,aend;
int c,k=1;
void dijkstra(){
fill(d,d+k+1,INF);
fill(visit,visit+k,false);
d[1]=0;
while(true){
int v=-1;
for(int u=1;u<=k;u++){//这里千万不能是n
if(!visit[u]&&(v==-1||d[u]<d[v])){
v=u;
}
}
if(v==-1){
break;
}
visit[v]=true;
for(int u=1;u<=k;u++){
if(!visit[u]&&e[v][u]!=INF){
if(d[u]>d[v]+e[v][u]){
d[u]=d[v]+e[v][u];
}
}
}
}
}
int main(){
while(cin>>n&&n!=-1){
mm.clear();
cin>>s>>aend;
//用map映射给站名标记，起始站为1，终点站为2
//怪不得之前的代码总是bug
k=1;//这里忘记初始化，every time 卡了那么久，原来是在这里
mm[s]=k++;
mm[aend]=k++;
//初始化e
for(int i=0;i<155;i++){
for(int j=0;j<155;j++){
if(i==j)
e[i][j]=0;
else
e[i][j]=INF;
}
}
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
if(!mm[a])
mm[a]=k++;
if(!mm[b])
mm[b]=k++;
if(c<e[mm[a]][mm[b]])
e[mm[a]][mm[b]]=e[mm[b]][mm[a]]=c;
}
if(s==aend)
cout<<"0"<<endl;
else{
dijkstra();
if(d[2]==INF)
cout<<"-1"<<endl;
else
cout<<d[2]<<endl;
}
}
return 0;
}
