Описание тега shortest-path

Shortest path problems are problems addressing finding the shortest path from a single source to a target source, usually in a graph.

Some of the commonly used shortest path algorithms are:

• Dijkstra's algorithm (single-source shortest path problem with no negative edge weights) dijkstra
• Bellman–Ford algorithm (single-source problem if edge weights may be negative) bellman-ford
• A* (A star) search algorithm (single pair shortest path using heuristics to try to speed up the search) a-star
• Floyd–Warshall algorithm (all pairs shortest paths) floyd-warshall
• Johnson's algorithm (all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs)
• Viterbi algorithm (shortest stochastic path problem with an additional probabilistic weight on each node)