|
转自：http://blog.sina.com.cn/s/blog_93d2ceba010145eq.html
一、（Prim算法求最小生成树）
|
语法：prim(GraphG,intvcount,intfather[]);
|
|
参数：
|
|
G：
|
图，用邻接矩阵表示
|
|
vcount：
|
表示图的顶点个数
|
|
father[]：
|
用来记录每个节点的父节点
|
|
返回值：
|
null
|
|
注意：
|
|
|
|
常数max_vertexes为图最大节点数
|
|
|
常数infinity为无穷大
|
|
源程序：
|
|
|
|
#defineinfinity1000000
#definemax_vertexes5
typedefintGraph[max_vertexes][max_vertexes];
voidprim(GraphG,intvcount,intfather[])
{
inti,j,k;
intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes];
for(i=0;i<vcount;i++)
{
lowcost[i]=G[0][i];
closeset[i]=0;
used[i]=0;
father[i]=-1;
}
used[0]=1;
for(i=1;i<vcount;i++)
{
j=0;
while(used[j])j++;
for(k=0;k<vcount;k++)
if((!used[k])&&(lowcost[k]<lowcost[j]))j=k;
father[j]=closeset[j];
used[j]=1;
for(k=0;k<vcount;k++)
if(!used[k]&&(G[j][k]<lowcost[k]))
{lowcost[k]=G[j][k];
closeset[k]=j;}
}
}
|
二、（Dijkstra算法求单源最短路径）
|
语法：result=Dijkstra(GraphG,intn,ints,intt,intpath[]);
|
|
参数：
|
|
G：
|
图，用邻接矩阵表示
|
|
n：
|
图的顶点个数
|
|
s：
|
开始节点
|
|
t：
|
目标节点
|
|
path[]：
|
用于返回由开始节点到目标节点的路径
|
|
返回值：
|
最短路径长度
|
|
注意：
|
|
|
|
输入的图的权必须非负
|
|
|
顶点标号从0开始
|
|
|
用如下方法打印路径：
i=t;
while(i!=s)
{
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
|
|
源程序：
|
|
|
|
intDijkstra(GraphG,intn,ints,intt,intpath[])
{
inti,j,w,minc,d[max_vertexes],mark[max_vertexes];
for(i=0;i<n;i++)mark[i]=0;
for(i=0;i<n;i++)
{d[i]=G[s][i];
path[i]=s;}
mark[s]=1;path[s]=0;d[s]=0;
for(i=1;i<n;i++)
{
minc=infinity;
w=0;
for(j=0;j<n;j++)
if((mark[j]==0)&&(minc>=d[j])){minc=d[j];w=j;}
mark[w]=1;
for(j=0;j<n;j++)
if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{d[j]=d[w]+G[w][j];
path[j]=w;}
}
returnd[t];
}
|
三、（Bellman-ford算法求单源最短路径）
|
语法：result=Bellman_ford(GraphG,intn,ints,intt,intpath[],intsuccess);
|
|
参数：
|
|
G：
|
图，用邻接矩阵表示
|
|
n：
|
图的顶点个数
|
|
s：
|
开始节点
|
|
t：
|
目标节点
|
|
path[]：
|
用于返回由开始节点到目标节点的路径
|
|
success：
|
函数是否执行成功
|
|
返回值：
|
最短路径长度
|
|
注意：
|
|
|
|
输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0
|
|
|
顶点标号从0开始
|
|
|
用如下方法打印路径：
i=t;
while(i!=s)
{
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
|
|
源程序：
|
|
|
|
intBellman_ford(GraphG,intn,ints,intt,intpath[],intsuccess)
{
inti,j,k,d[max_vertexes];
for(i=0;i<n;i++){d[i]=infinity;path[i]=0;}
d[s]=0;
for(k=1;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}
success=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[j]>d[i]+G[i][j])return0;
success=1;
returnd[t];
}
|
四、（Floyd-Warshall算法求每对节点间最短路径）
|
语法：Floyd_Washall(GraphG,intn,GraphD,GraphP);
|
|
参数：
|
|
G：
|
图，用邻接矩阵表示
|
|
n：
|
图的顶点个数
|
|
D：
|
D[i,j]表示从i到j的最短距离
|
|
P：
|
P[i,j]表示从i到j的最短路径上j的父节点
|
|
返回值：
|
null
|
|
源程序：
|
|
|
|
voidFloyd_Washall(GraphG,intn,GraphD,GraphP)
{
inti,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{D[i][j]=G[i][j];
P[i][j]=i;}
for(i=0;i<n;i++){D[i][i]=0;P[i][i]=0;}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(D[i][j]>D[i][k]+D[k][j])
{D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[k][j];}
}
|
|
转播
