Dijskstraアルゴリズム
9430 ワード
#include
#include
#include
#include
using namespace std;
const int maxn = 10000;
const int INF = 1<<30;
struct node
{
int x,d;
node() {}
node(int a,int b)
{
x=a;
d=b;
}
bool operator < (const node & a) const
{
if(d==a.d) return x// d ,x
else return d > a.d;
}
};
vector eg[maxn];
int dis[maxn],n;
void Dijkstra(int s)
{
int i;
for(i=0; i<=n; i++) dis[i]=INF;
dis[s]=0;
// ,
priority_queue q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node x=q.top();
q.pop();
for(i=0; i)
{
node y=eg[x.x][i];
if(dis[y.x]>x.d+y.d)
{
dis[y.x]=x.d+y.d;
q.push(node(y.x,dis[y.x]));
}
}
}
}
int main()
{
int a,b,d,m;
while(scanf("%d%d",&n,&m))
{
for(int i=0; i<=n; i++) eg[i].clear();
while(m--)
{
scanf("%d%d%d",&a,&b,&d);
eg[a].push_back(node(b,d));
eg[b].push_back(node(a,d));
}
Dijkstra(1);
for(int i=1; i<=n; i++)
printf("%d ", dis[i]);
}
return 0;
}
//6 9//1 2 1//1 3 12//2 3 9//2 4 3//3 5 5//4 3 4//4 5 13//4 6 15//5 6 4////0 1 8 4 13 17
優先キューの最適化
シンプルなバージョンで、時間の複雑さは上記より高いです
#include
int e[10][10];
int dis[10];
int book[10];
int main()
{
int n, m;
int inf=99999999;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
int t1, t2, t3;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d", &t1, &t2, &t3);
e[t1][t2]=t3;
}
for(int i=1; i<=n; i++)
{
dis[i]=e[1][i];
}
int u, min;
book[1]=1;
for(int i=1; i<=n; i++)
{
min=inf;
for(int j=1; j<=n; j++)
{
if(dis[j]0 )
{
u=j;
min=dis[j];
}
}
book[u]=1;
for(int v=1; v<=n; v++)
{
if(e[u][v]dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];
}
}
}
for(int i=1; i<=n; i++)
printf("%d ", dis[i]);
}
転載先:https://www.cnblogs.com/dongdong25800/p/9630613.html