算法及编程语言 - 声振论坛 - 振动,动力学,声学,信号处理,故障诊断 - Powered by Discuz! Archiver

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

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

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

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

页: [1]

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