What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

Question

I am looking for the most efficient algorithm for finding shortest path between two Vertices.

The graph is:

• undirected
• edge-weighted
• Non-negative
• less then 300 nodes

I understand that most of the algorithms based on Dijkstra's shortest path algorithm. But which one is the most efficient for the case a specified above. Thank you.

• D.W.: What algorithms have you considered? When you say "most efficient", do you care about theoretical running time or practical efficiency? What have you tried? For 300 nodes, it's not going to matter: that's a tiny graph, and anything reasonable will be super-fast.
• Firstname Lastname: I am considering A*, Dijsktra's, Bellman–Ford algorithm... As I am reading on Wikipedia about it, it just says about directed graphs. Bellman–Ford algorithm can be used with negative graphs but slower then Dijkstra's. Getting confused more and more. I care about theoretical time (300 nodes at the beginning, might increase later on).
• Danny: Djikstras should be very reasonable for your interests. If you want some more fun: Fibonacci-Heaps are a quite good data structure to speed things up.
• D.W.: The theoretical running time of those is all covered in standard textbooks and online resources (e.g., Wikipedia), so it seems like you have everything to answer your question on your own. Please edit your question to show your work: show what algorithms you've considered, what their running time is, which seems to be the best, and identify what your remaining question is.
• Juho: @Danny I'm not sure Fibonacci heaps are that fast in practice though (there should be other alternative though).

Answer 1

Use Dijkstra's algorithm. It is quite efficient, and on a graph with only 300 nodes, it will run extremely fast, so fast that it's not worth worry about.

You mentioned in a comment that your main concern is that the algorithms are described for directed graphs, but you have an undirected graph. No worries. You can apply Dijkstra's algorithm to an undirected graph, too. Whenever your graph has an undirected edge between vertices $u$ and $v,ドル think of that as equivalent to the two directed edges $u \to v$ and $v \to u$. In this way, you can convert your undirected graph to a directed graph -- and then you can apply Dijkstra's algorithm to the result. The same goes for any other algorithm for directed graphs; it can be applied to an undirected graph in the same way.