迪杰斯特拉 无向图 邻接表

发布网友 发布时间：2022-03-27 09:48

我来回答

共3个回答

热心网友 时间：2022-03-27 11:17

我的数据读入是n个点，m条边，以下m行描述为 x 与 y之间有一条权值为z的边

#include<iostream>
using namespace std;
const int MAX=0xfffffff;
struct xyz
{int to,v;}map[101][101]={0};
int dis[101]={0},n,m,pre[101]={0},sum[101]={0},st,ed;
bool f[101]={0};
void init()
{
int i,j,x,y,z;
scanf("%d%d",&n,&m);
for( i=1;i<=100;i++)for(j=1;j<=100;j++)map[i][j].v=MAX;
for( i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
map[x][++sum[x]].to=y;
map[x][sum[x]].v=z;
map[y][++sum[y]].to=x;
map[y][sum[y]].v=z;
}
cin>>st>>ed;
}
void out(int n)
{
if(pre[n]==0){printf("%d ",n); return ;}
out(pre[n]);
printf("%d ",n);
}
void dijsktra(int st)
{
int i,j,Min,k,t;
f[st]=1;
for( i=1;i<=n;i++)dis[i]=MAX;
for( i=1;i<=sum[st];i++){ t=map[st][i].to; dis[t]=map[st][i].v; }
for( i=1;i<=n;i++)
{
Min=MAX;
k=0;
for(j=1;j<=n;j++)
if(!f[j]&&dis[j]<Min){Min=dis[j];k=j;}
f[k]=1;
for( j=1;j<=sum[k];j++)
{
t=map[k][j].to;
if( !f[t]&&dis[k]+map[k][j].v<dis[t])
{
dis[t]=dis[k]+map[k][j].v;
pre[t]=k;
}
}
}
printf("%d\n",dis[ed]);
printf("%d ",st);out(ed);
}
int main()
{
init();
dijsktra(st);
return 0;
}

热心网友 时间：2022-03-27 12:35

include<iostream>
#include<cmath>
using namespace std;
const int maxint=0xfffffff;
struct xyz
{int x,y;double d;}a[101];
int s,t,f[101]={0},n,m;
double map[101][101]={0},ds[101];
double cal(int x,int y)
{return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));}
void init()
{
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
scanf("%d",&m);
for(i=1;i<=m;i++){scanf("%d%d",&x,&y);map[x][y]=map[y][x]=cal(x,y);}
scanf("%d%d",&s,&t);
}
void dijsktra()
{
int i,j,minn,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(map[i][j]==0)map[i][j]=maxint;
for(i=1;i<=n;i++)ds[i]=map[s][i];
for(i=1;i<=n;i++)
{minn=maxint;
k=0;
for(j=1;j<=n;j++)
if(!f[j]&&ds[j]<minn){minn=ds[j];k=j;}
f[k]=1;
for(j=1;j<=n;j++)
if(!f[j]&&ds[k]+map[k][j]<ds[j])ds[j]=ds[k]+map[k][j];
}
printf("%.2lf",ds[t]);
}
int main()
{
init();
dijsktra();
return 0;
}

热心网友 时间：2022-03-27 14:10

http://e.codepub.com/2009/0603/5414.php

这个很详细