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?
1 Answer
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: