1
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 9, 2015 at 17:25
  • $\begingroup$ 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). $\endgroup$
    – Firstname Lastname
    Dec 9, 2015 at 17:37
  • $\begingroup$ 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. $\endgroup$
    – Danny
    Dec 9, 2015 at 17:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 9, 2015 at 18:14
  • $\begingroup$ @Danny I'm not sure Fibonacci heaps are that fast in practice though (there should be other alternative though). $\endgroup$
    – Juho
    Dec 9, 2015 at 19:06

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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