search

purpleprotocol / graphlib

Simple but powerful graph library for Rust
MIT License
193 stars 14 forks source link

Add shortest path iterator #5

Open octavonce opened 5 years ago

octavonce commented 5 years ago

In order to support more use cases, we can add a shortest path between two nodes iterator.

cherrygot-personal commented 5 years ago

What should be preferred? Bellman–Ford or Dijkstra's algorithm. Or both!

octavonce commented 5 years ago

Yes! We can certainly do both!

We can expose them as Graph::bellman_ford() and Graph::dijkstra().

cherrygot-personal commented 5 years ago

I was trying to implement the Dijkstra algorithm, but found that there is no method to get the weight of edge between two vertices. Maybe you can help. If I have 'VertexId's of two nodes, how would I know weight of edge between them?

octavonce commented 5 years ago

Maybe we need to do these first: #4 #3 and also include a Graph::weight method which receives as parameters two VertexId structs.

cemeyer commented 2 years ago

Graph::dijkstra() and iterator::Dijkstra exist now.

saona-raimundo commented 2 years ago

Sorry if this is out of nowhere, but would it not be a more productive approach to implement the traits in petgraph to get access to all their algorithms implemented in petgraph::algo?

Is it because of the no-std option that this route was not taken?