2
$\begingroup$

I have a triangle matrix NxN of distances between vertices (vertex i connected only with vectices j>i) and I'd like to sample path from first to the last and use it as a training sample. Is there an algorithm to do it? Would swapping min->sample in A* be sufficient?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't know whether this answers your question. But have a look in these algorithms:

The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.

Dijkstra's algorithm solves the shortest-path problem for any weighted, directed graph with non-negative weights. It can handle graphs consisting of cycles, but negative weights will cause this algorithm to produce incorrect results.

The Shortest Path algorithm calculates the shortest (weighted) path between a pair of nodes. In this category, Dijkstra's algorithm is the most well known. It is a real time graph algorithm, and can be used as part of the normal user flow in a web or mobile application.

More Info at:

  1. https://www.sciencedirect.com/topics/computer-science/shortest-path-problem
  2. https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e
  3. https://link.springer.com/chapter/10.1007/978-3-319-05813-9_9
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.