來自petgraph的算法會找到從A到B的最短路徑？

我有一個方向圖，希望找到從節點A到節點B的最短路徑。我搜索了crates.io，發現了petgraph，看起來像最受歡迎的箱子。它implements a number of algorithms，但他們都沒有解決我的任務。我錯過了什麼？來自petgraph的算法會找到從A到B的最短路徑？

例如，Dijkstra's algorithm返回路徑成本，但哪條路徑具有最低成本？ Bellman-Ford algorithm返回路徑成本和節點，但沒有路徑。

這是我發現從圖形打印路徑最簡單的方法：

extern crate petgraph; 
use petgraph::prelude::*; 
use petgraph::algo::dijkstra; 

fn main() { 
    let mut graph = Graph::<&str, i32>::new(); 
    let a = graph.add_node("a"); 
    let b = graph.add_node("b"); 
    let c = graph.add_node("c"); 
    let d = graph.add_node("d"); 

    graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]); 
    let paths_cost = dijkstra(&graph, a, Some(d), |e| *e.weight()); 
    println!("dijkstra {:?}", paths_cost); 

    let mut path = vec![d.index()]; 
    let mut cur_node = d; 

    while cur_node != a { 
     let m = graph 
      .edges_directed(cur_node, Direction::Incoming) 
      .map(|edge| paths_cost.get(&edge.source()).unwrap()) 
      .min() 
      .unwrap(); 
     let v = *m as usize; 
     path.push(v); 
     cur_node = NodeIndex::new(v); 
    } 

    for i in path.iter().rev().map(|v| graph[NodeIndex::new(*v)]) { 
     println!("path: {}", i); 
    } 
}

據我所看到的，我需要的基礎上， dijkstra結果來計算路徑自己。

我相信，如果我實現由自己dijkstra（立足dijkstra.rs我的實現），並與predecessor取消註釋行，並返回predecessor，最終變種會更快，因爲答案會像predecessor[predecessor[d]]。

來源

2017-04-14 user1244932

通過你最後一句，你似乎缺乏瞭解Dijkstra和Bellman-Ford算法。我建議你先研究它們及其結果。 –

@ E_net4我不明白你，我看Dijkstra的實現（https://github.com/bluss/petgraph/blob/master/src/dijkstra.rs），他們只是評論包含結果路徑的hashmap，並且不返回這條路。 Dijkstra實施的知識如何幫助我？ – user1244932

請包括你在你的問題中試過的東西。如果特定API有問題，請指出。 –

由於mentioned in the comments（由庫的主要作者，不會少），你可以使用A *（astar）算法：

extern crate petgraph; 

use petgraph::prelude::*; 
use petgraph::algo; 

fn main() { 
    let mut graph = Graph::new(); 

    let a = graph.add_node("a"); 
    let b = graph.add_node("b"); 
    let c = graph.add_node("c"); 
    let d = graph.add_node("d"); 

    graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]); 

    let path = algo::astar(
     &graph, 
     a,    // start 
     |n| n == d,  // is_goal 
     |e| *e.weight(), // edge_cost 
     |_| 0,   // estimate_cost 
    ); 

    match path { 
     Some((cost, path)) => { 
      println!("The total cost was {}: {:?}", cost, path); 
     } 
     None => println!("There was no path"), 
    } 
}

The total cost was 2: [NodeIndex(0), NodeIndex(1), NodeIndex(3)]

來源

2017-10-22 14:09:37 Shepmaster

來自petgraph的算法會找到從A到B的最短路徑？

回答

相關問題