0

两个简单的问题，我的大脑不工作了。我正在使用弗洛伊德算法并尝试重建从顶点 U 到顶点 V 的路径。这是我重建路径的代码。

public List<Integer> findCheapestPath(int u, int v)
{
    if (u >= adjMatrix.length || v >= adjMatrix.length || u < 0 || v < 0)
    {
        throw new IllegalArgumentException("Error--Illegal Arugment Exception: One of the verticies are not valid.");
    }
    int intermediate;

    intermediate = path[u][v];
    if (intermediate == -1)
    {
        pathList.add(u);
        return pathList;
    } else
    {
        findCheapestPath(u, intermediate);
        findCheapestPath(intermediate, v);
    }
    return pathList;
}

举个例子，让 u = 0 和 v = 3，并让从 0 到 3 的最短路径为 0,1,2,3。但是我有两个问题。我的 pathList 是该类的实例变量，并且：

  1. 我希望列表返回“0,1,2,3”，但它只返回“0,1,2”，或者如果我用 pathList.add(v) 替换 pathList.add(u)，那么它只返回“ 1,2,3" 我不知道如何让它返回整个路径，包括两个末端顶点。尝试放置 pathList.add(other vertex) 将导致它复制每个中间顶点。
  2. 当我再次调用该方法时，让 u = 3 和 v = 0，并让从 3 到 0 的最短路径为“3,0”（已经是最短路径），它只是添加到我之前的列表中，导致我的错误从上面的 “0,1,2,3”或“1,2,3,0”当它应该只是“3,0”时

有什么帮助吗？

4

1 回答 1

0

不要使用类变量，并制作一个包装函数。

更详细地说，将您的函数更改为此签名：

private List<Integer> findCheapestPathInner(int u, int v, pathList)

（显然还更改了其中的递归调用以适应新签名），并创建另一个函数：

public List<Integer> findCheapestPath(int u, int v) {
  List<Integer> pathList = new ArrayList<Integer>();
  pathList.add(u);
  return findCheapestPathInner(u, v, pathList);
}
于 2012-05-11T00:39:26.697 回答