0

我创建了这个算法来获得地图上两个选定点之间的最短点。

首先，我用距离、重量完全填充了矩阵。我命名它，例如：dist[0,1] 指的是点 0 和点 1 之间的道路。每个点都有一个分配给它的数字。

矩阵都相应地填充，然后 Fjord Warshall 算法运行：

for (int k = 0; k < count; ++k)
            {
                for (int i = 0; i < count; ++i)
                {
                    for (int j = 0; j < count; ++j)
                    {
                        if (dist[i,j] > (dist[i,k]+dist[k,j]))
                        {
                            dist[i, j] = dist[i, k] + dist[k, j];
                        }
                    }
                }
            }

这得出了每条路径之间的最短点。然后我检查我拥有的路径以获得它的最短点：

                shortest = dist[x, y];

哪个返回正确的值，一切正常。这是我的问题。我需要将其设置为查看它通过哪些点。我的意思是，如果我想从点 1 到点 5，并且最短的路线是通过 3 和 6，它将显示 1、3、6、5。

有任何想法吗？完全卡在了这个上。

4

1 回答 1

3

创建另一个与 dist 具有相同维度的数组，我们称之为 vert。

下线：

dist[i, j] = dist[i, k] + dist[k, j];

添加，

vert[i, j] = k;

然后调用定义为的递归函数，

void pr(int x, int y)
{
    if(x == y)
        return;
    pr(x, vert[x, vert[x, y]]);
    cout << vert[x, y];
    pr(vert[vert[x, y]], y);
}
于 2014-05-16T21:09:57.307 回答