[求助]有没蝈蝈能帮我找一下用C或C++编的最短路加权算法啊。

ggf1105 · 发表于 2006-3-23 16:45

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

Floyd-Warshall算法： 其源代码为：
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MAXSIZE 20
void Floyd(int [][MAXSIZE],int [][MAXSIZE],int);
void display_path(int [][MAXSIZE],int [][MAXSIZE],int);
void reverse(int [],int);
void readin(int [][MAXSIZE],int *);
#define MAXSUM(a,b) (((a)!=INT_MAX&&(b)!=INT_MAX)?((a)+(b)):INT_MAX)
void Floyd(int dist[][MAXSIZE],int path[][MAXSIZE],int n)
{ 
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
path[j]=i;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dist[j]>MAXSUM(dist[k],dist[k][j]))
{
path[j]=path[k][j];
dist[j]=MAXSUM(dist[k],dist[k][j]);
}
}
void disp_path(int dist[][MAXSIZE],int path[][MAXSIZE],int n)
{
int *chain;
int count;
int i,j,k;
printf(“\n\norigin->Dest Dist Path”);
printf(“\n-------------- ---- ----”);
chain=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
{
printf(“\n%6d->%4d”,i+1,j+1);
if(dist[j]==INT_MAX)
printf(“NA”);
else
{
printf(“%4d”,dist[j]);
count=0;
k=j;
do{ k=chain[count++]=path[k];}
while(i!=k);
reverse(chain,count);
printf(“%d”,chain[0]+1);
for(k=1;k<count;k++)
printf(“->%d”,chain[k]+1);
printf(“->%d”,j+1);
}
}
}
free(chain);
}
#define SWAP(a,b)
{temp=a;a=b;b=temp;}
void reverse(int x[],int n)
{
int i,j,temp;
for(i=0,j=n-1;i<j;i++,j--)
SWAP(x,x[j]);
}
void readin(int dist[][MAXSIZE],int *number)
{
int origin,dest,length,n;
int i,j;
char line[100];
gets(line);
sscanf(line,”%d”,&n);
*number=n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
dist[j]=INT_MAX;
dist=0;
}
gets(line);
sscanf(line,”%d%d%d”,&origin,&dest,&length);
while(origin!=0&&dest!=0&&length!=0)
{
dist[origin-1][dest-1]=length;
gets(line);
sscanf(line,”%d%d%d”,&origin,&dest,&length);
}
}} 谁能帮我写一个主函数，这是没加权的，不知道加权的怎么修改。 谢谢哈

账号		自动登录	找回密码
密码			我要加入

[经典算法] [求助]有没蝈蝈能帮我找一下用C或C++编的最短路加权算法啊。

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。