《数据结构与算法》——最小路径
本帖最后由 luciferzf 于 2017-8-19 19:01 编辑最短路径：
1）迪杰斯特拉算法：以贪心算法为核心，分为三部分，用三个数组P,D,FINAL分别储存路径长度，各个定点的前驱定点，各个定点的遍历情况。
首先，进行初始化，P=0，D=0，FINAL=1;
然后进行循环，找到当前定点i相邻定点的最短边l，将p+l赋值给p；
再循环D数组，如果发现经过i点的更短路径，则更新p的值，并修改FINAL的值。
重复三个步骤直至遍历完终点定点。
2）弗洛伊德算法：比起迪杰斯特拉算法，弗洛伊德算法时间复杂度要更高，因为弗洛伊德算法计算的是所有点的最小路径。
算法相比，弗洛伊德算法要比迪杰斯特拉算法多一个循环，用以遍历每个定点到其他定点的最小路径必须经过的定点
void ShortestPath_Dijkstar(MGraph G,int VG,Pathare *P,ShortPathTable *D)
{
int v,w,k,min;
int final;
for(v=0;v<G.numVertexes;v++)
{
final=0;
(*D)=G.arc;
(*P)=0;
}
(*D)=0;
final=1;
for(v=0;v<G.numVertexes;v++)
{
min=INFINTE;
for(v=0;v<G.numVertexes;v++)
{
if(!final&&(*D)<min)
{
k=w;
min=(*D);
}
}
final=1;
for(w=0;w<G.numVertexes;w++)
{
if(!final&&(min+G.arc<(*D)))
{
(*D)=min+G.arc;
(*p)=k;
}
}
}
}
页:
[1]