0

Two simple questions and my brain's not working. I'm using Floyd's Algorithm and trying to reconstruct the path taken from vertex U to vertex V. Here's my code to reconstruct the path.

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;
}

For one example, let u = 0 and v = 3, and let the shortest path from 0 to 3 be 0,1,2,3. However I have two problems. My pathList is an instance variable of the class and:

  1. I want the list to return "0,1,2,3" but it only returns "0,1,2", or if i replace pathList.add(u) with pathList.add(v), then it returns only "1,2,3" I could not figure out how to make it return the entire path including both end vertices. trying to put pathList.add(other vertex) will cause it to duplicate every intermediate vertex.
  2. When I call the method again, letting u = 3 and v = 0, and let the shortest path from 3 to 0 be "3,0" (already the shortest path), it just adds onto my previous list making it with my error from above "0,1,2,3" or "1,2,3,0" when it's supposed to be just "3,0"

Any help?

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 に答える