如何正確使用DijkstraDistance復位

我有一些節點和鏈路的UndirectedSparseGraph克，然後我需要的最短路徑和計算的函數：如何正確使用DijkstraDistance復位

alg = new DijkstraDistance<Long, String>(g); 
// 
alg.enableCaching(false); 
// 
for(Node n:g.getVertices()){ 
    for(Node m:g.getVertices(){ 
     findAValue(alg.getDistance(n, m)); 
    } 
}

然後我通過加入邊緣，或刪除更新圖表一個邊緣，如：

g.addEdge(id, n, m, EdgeType.UNDIRECTED);

現在我該怎麼做才能再次計算距離？如果我只需要輸入：

alg = new DijkstraDistance<Long, String>(Hummon.g);

，或者我應該做的更好：

alg.reset(); 
alg = new DijkstraDistance<Long, String>(Hummon.g);

我加入了去除邊緣到圖形的距離來計算很多次，所以我真的希望使用最有效的方法。

BTW：有什麼樣.update（）的距離是多少？提前致謝！

來源

2014-05-18 user299791

您將要刪除'ALG =新DijkstraDistance <長整型，字符串>（Hummon.g）;'在第二個例子。如果你想用一個全新的實例來替換它，那麼在第一個實例中重置就沒有意義了。 –

所以剛剛調用reset（）會更新距離？ – user299791

我不知道 - 我不熟悉榮格圖書館。但是，如果在一個對象上調用'reset'，那麼它將不會比你第一個沒有調用'reset'的例子效率更高。我會做一個單元測試，檢查一些結果，然後檢查它是否仍然成功，當你改變你重新計算的方式。在'DijkstraDistance'上有一個'reset（V source）'方法，如果你只添加或移除一個頂點的邊緣，效率看起來更有希望。 –

@Erwin Bolwidt的建議下，我已經測試.reset段（）與此代碼：

g = new UndirectedSparseGraph<Long, String>(); 
    // add some vertices 
    for(long i=0;i<5;i++){ 
     g.addVertex(i); 
    } 
    // add some edges 
    g.addEdge("0-1", 0l, 1l, EdgeType.UNDIRECTED); 
    g.addEdge("0-2", 0l, 2l, EdgeType.UNDIRECTED); 
    g.addEdge("1-3", 1l, 3l, EdgeType.UNDIRECTED); 
    g.addEdge("3-4", 3l, 4l, EdgeType.UNDIRECTED); 
    alg = new DijkstraDistance<Long, String>(g); 
    for(Long n:g.getVertices()){ 
     for(Long m:g.getVertices()){ 
      System.out.println(n+"-"+m+" dist "+alg.getDistance(n, m)); 
     } 
    } 
    System.out.println("TOPA\n\n\n"); 
    g.addEdge("2-4", 2l, 4l, EdgeType.UNDIRECTED); 
    alg.reset(2l); 
    for(Long n:g.getVertices()){ 
     for(Long m:g.getVertices()){ 
      System.out.println(n+"-"+m+" dist "+alg.getDistance(n, m)); 
     } 
    }

很容易地看到，.reset段（）更新的距離。

來源

2014-05-18 13:51:24 user299791

如何正確使用DijkstraDistance復位

回答

相關問題