最简单的最短路径
上代码……
dijkstra实现
#include<iostream>
using namespace std;
#define MAX 0x7fffffff
int map[1001][1001];
bool s[1001];
int d[1001];
int n,t;
int sum;
void dijkstra(int v)
{ int a,b,c;
int i,j,k;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{ map[i][j]=MAX;
}
}
for(i=1;i<=t;i++)
{ scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
map[a][b]=map[b][a]=c;
}
for(i=1;i<=n;i++)
d[i]=map[v][i];
d[v]=0;
s[v]=1;
for(i=1;i<n;i++)
{ int min=MAX;
for(j=1;j<n;j++)
{
if(!s[j]&&d[j]<min&&d[j]>0)
{ k=j;
min=d[j];
}
}
s[k]=1;
for(j=1;j<=n;j++)
{ if(!s[j]&&d[k]+map[k][j]<d[j]&&map[k][j]<MAX)
{ d[j]=d[k]+map[k][j];
}
}
}
}
int main()
{
scanf("%d%d",&t,&n);
dijkstra(1);
printf("%d\n",d[n]);
system("pause");
return 0;
}
spfa实现
#include<iostream>
using namespace std;
#define MAX 1001
#define maxx 0x7fffffff
int map[1001][1001];
int n,t;
int q[10*MAX];
int flag[MAX];
int d[MAX];
int spfa(int v)
{ memset(flag,0,sizeof(flag));
int rear,front;
int now;
int i,j;
for(i=1;i<=n;i++)
d[i]=maxx;
d[v]=0;
rear=front=0;
q[rear++]=v;
flag[v]=1;
while(front<=rear)//队列不为空
{
now=q[front++];
flag[now]=0;
for(i=1;i<=n;i++)
{
if(map[now][i]<maxx&&map[now][i]>0)
{ if(d[now]+map[now][i]<d[i])
{ d[i]=d[now]+map[now][i];
if(!flag[i])
{ flag[i]=1;
q[rear++]=i;
}
}
}
}
}
return 0;
}
int main()
{ int i,j;
int a,b,c;
scanf("%d%d",&t,&n);
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{ map[i][j]=maxx;
}
}
for(i=1;i<=t;i++)
{ scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
map[a][b]=map[b][a]=c;
}
spfa(1);
printf("%d\n",d[n]);
system("pause");
return 0;
}
dijkstra用堆实现
#include<iostream>
using namespace std;
#define N 1001
#define MAX 0x7fffffff
int h[N];
int map[N][N];
int d[N];
int t,n;
int a,b,c;
int size;
void minheap(int i)
{ int l=2*i;
int r=2*i+1;
int small=i;
if(l<=size&&d[h[i]]>d[h[l]])
{ small=l;
}
if(r<=size&&d[h[small]]>d[h[r]])
{ small=r;
}
if(small!=i)
{ int tmp=h[i];
h[i]=h[small];
h[small]=tmp;
minheap(small);
}
}
void build()
{ int i;
size=n;
for(i=1;i<=size;i++)
h[i]=i;
for(i=(size>>1);i>=1;i--)
{ minheap(i);
}
}
int minsolve()
{
int minn=h[1];
h[1]=h[size];
size--;
minheap(1);
return minn;
}
void de(int i,int key)
{
d[h[i]]=key;
while(d[h[i]]<d[h[i/2]]&&i>1)
{
int tmp=h[i];
h[i]=h[i/2];
h[i/2]=tmp;
i/=2;
}
}
void solve(int v)
{
int i,j;
for(i=1;i<=n;i++)
{ d[i]=MAX;
}
d[v]=0;
build();
while(size>=1)
{ int u=minsolve();
for(i=1;i<=size;i++)
{ if(map[u][h[i]]<MAX&&d[u]+map[u][h[i]]<d[h[i]])
{ de(i,d[u]+map[u][h[i]]);
}
}
}
}
int main()
{ scanf("%d%d",&t,&n);
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=MAX;
}
}
for(i=1;i<=t;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
map[a][b]=map[b][a]=c;
}
solve(1);
printf("%d\n",d[n]);
system("pause");
return 0;
}