Shortest path in a directed, weighted graph with set number of weights

Question

Lets say there is a graph (V,E) that is directed and weighted.

The weights of every edge in the graph are 1 or 2 or 3.

What would be a quick and efficient algo to find the shortest path? Thanks in advance!!

Answer 1

Dijkstra's algorithm would likely still have near-optimal performance, and has the advantage of being fairly simple.

However, for a graph with small integer weights, you can use more complicated versions of the (fibonacci) heap used in Dijkstra that have better asymptotic performance. Specifically, consider this work by Mikkel Thorup which solves single-source shortest path in O(|E| + |V| log log |C|) where E is the set of edges, V is the set of vertices and C is the largest weight. In your case C is constant, which turns the asymptotic complexity into O(|E| + |V|).

Do note that this is mostly of theoretical interest, and is unlikely to give any significant speedup over a simpler algorithm.

Answer 2

There a list of algorithms for the Shortest path problem:

• Dijkstra's algorithm
• A* search algorithm
• ...etc

you can find a list in this Wikipedia page about Shortest path problem Algorithms

you can test and play with this online Dijkstra Shortest Path visualization.

a very interesting Pathfinding-Visualizer to see how some algorithms explore the research space to reach the goal is in github Pathfinding-Visualizer , this will give you a general idea on th differences between algorithms visually. Note: Pathfinding doesn't mean the shortest path; it's depend on the used algorithm.