Geek Answers Handbook

Which algorithm is best to move a weighted, directional graph that provides the start and end points?

Hi, I’m looking for the best algorithm to find the optimal path that goes along an oriented and weighted graph.

[Hello everyone, I am editing the problem to fully explain my requirement]

For example: if in a graph of 5 nodes (let’s assign a number 1,2,3,4,5 for all 5 nodes, respectively), if I want to start crawling from node 2 and eventually to 4, covering all nodes, then which one is the best algorithm to solve the problem?

We can have two assumptions:

a) An edge always exists between any two nodes. (for two nodes (A and B) there is an edge from A to B and from B to A.

b) we can cross a node twice (if it is necessary to go through the full schedule).

+4
source share
2 answers

This is a classic computer science problem with a well-known solution.

Are there only graphs without negative boundaries? Then use the Dijkstras or A * algorithm . Otherwise, use the Bellman-Ford algorithm . If you want to find all pairs of shortest paths between all nodes, use the Floyd and Warshall algorithm .

+5
source

Using Dijkstra is the way to go, but you can configure the algorithm (which by default is the only source - the multiple sink algorithm) - the implementation of a single-threaded single-threaded system.

, node ( node), , . . , . , , , . .

+2

More articles:


All Articles