// 假设现在只允许经过1号顶点,求任意两点之间的最短路径,只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可
// e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点,再从1号顶点
// 到j号顶点的路程之和, 其中i是1->n循环,j也是1->n循环
// 只允许经过1号节点,任意两点之间的最短路径 (采用二维矩阵表示图)
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(e[i][j] > e[i][1] + e[1][j])
e[i][j] = e[i][1] + e[1][j];
}
}
// 接下来继续求只允许1和2号两个顶点的情况下任意两点之间的最短路径,只需要在允许进过1号顶点时任意两点的最短路径的
// 结果下,再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短,即e[i][2]+e[2][j]是否比
// e[i][j]要小
// 经过1号顶点
for(i=1; i<=n; j++)
for(j=1; j<=n; j++)
if(e[j][j] > e[i][1]+e[1][j])
e[j][j] = e[i][1] + e[1][j];
// 经过2号顶点
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(e[i][j] > e[i][2]+e[2][j])
e[i][j] = e[i][2] + e[2][j];
本内容试读结束,登录后可阅读更多
下载后可阅读完整内容,剩余1页未读,立即下载