# Dijkstra's algorithm: choosing which point to begin with

Gold Member
In Dijkstra's algorithm (for an efficient way to find the shortest path between two given vertices, or nodes, in a graph), the only freedom the programmer has is to name which of the two given vertices one begins with. Is there any efficient way to tell which one of the two one should start with? That is, the answer will obviously be the same, but the total computing time, or number of steps, is likely to be different, according to one's choice.

You mean, you want to first apply an algorithm to find out where start from and second apply the real algorithm? I guess that is possible if at the end provides savings.

The very first thing the occurs to me is to start on the node with the least number of connections. In any case, have you simply tried running the program and starting from one node and then starting from the other and see if there are real savings?

Is your graph bi-directional? I presume your worry is a moot point for a directional graph where if you want to go from A to B, you would really need to start from A, I guess.

my 2 cents

• Gold Member
Thanks for your 2 cents, gsal. I will now convert it to local currency....:)
Yes, I would ideally first run a program that did not cost too much (in computer time) in order to select which one of the two given points to use as starting points, and then run the full algorithm. I am referring to an undirected (bidirectional) graph. Running the algorithm on a test graph or two to see which one comes out better is not sufficient -- there is no guarantee that the result of a couple of graphs will work on other graphs. Also there may be other factors that how many connections there are at first.... I am not convinced that starting with the end with fewest connections is necessarily the best.

Well...I just read a bit of the Wikipedia page for Dijkstra's algorightm...I guess I should have done that in the first place...anyway, it does not seem that complicated at all and it is exhaustive; so, I don't know what kind of algorithm you would initially apply just to find out where to start...may as well start applying Dijkstra's right away.

So, I guess that if you start on node A, you get one SPT starting on A; and if you start on B, you get a SPT starting on B....BUT, I presume the path connecting A to B would be exactly the same on both trees.

One thing you COULD do to improve solution time is to cut Dijkstra's loops short...in other words, if all you want is A to B and not the entire tree...as soon as both A and B are in the solved for set, you can quite the do-loops.

• 