単一ソース最短パス---Dijkstraアルゴリズム--パス復元
1877 ワード
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;
const int maxn=100;
const int INF=999999;
int pre[maxn];
bool visited[maxn];
int d[maxn],cost[maxn][maxn],n,m; //n vertexs,1,2,...n. m edges.
void dijkstra(int s)
{
memset(pre,-1,sizeof(pre));
fill(d+1,d+1+n,INF);
memset(visited,0,sizeof(visited));
d[s]=0;
while(1)
{
int index=-1;
for(int u=1;u<=n;u++){
if(!visited[u] && (index==-1|| d[u]<d[index]))
index=u;
}
if(index==-1)break;
visited[index]=1;
for(int u=1;u<=n;u++){
if( d[u]>d[index]+cost[index][u])
{
d[u]=d[index]+cost[index][u];
pre[u]=index;
}
}
}
}
vector<int> get_path(int t)
{
vector<int> path;
path.clear();
for(;t!=-1;t=pre[t])
{
path.push_back(t);
}
reverse(path.begin(),path.end());
return path;
}
int main()
{
ifstream fin;
fin.open("input.txt");
cout<<fin.is_open()<<endl;
while(fin>>n>>m)
{
for(int i=1;i<=n;i++) //
for(int j=1;j<=n;j++){
if(i==j)cost[i][j]=0;
else cost[i][j]=INF;
}
for(int i=1;i<=m;i++)
{
int u,v,c;
fin>>u>>v>>c;
cost[u][v]=c; //DAG
}
int s,t;
fin>>s>>t;
dijkstra(s);
cout<<"the shortest path from "<<s<<" to "<<t<<" is: "<<d[t]<<endl;
cout<<"the path is :"<<endl;
vector<int> path=get_path(t); //
for(int i=0;i!=path.size();i++)cout<<path[i]<<" ";
cout<<endl;
}
}
テストのセットを指定します.
5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60
1 5
出力結果:
1
the shortest path from 1 to 5 is :60
the path is :
1 4 3 5