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 回答