Dijkstra's algorithm: choosing which point to begin with

In summary: This algorithm does not take into account the values of the neighbors of the current node when finding the shortest path, which can cause it to freeze in indecision.
  • #1
nomadreid
Gold Member
1,668
203
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.
 
Technology news on Phys.org
  • #2
You mean, you want to first apply an algorithm to find out where start from and second apply the real algorithm? :confused: 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
 
  • Like
Likes nomadreid
  • #3
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.
 
  • #4
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.
 
  • Like
Likes nomadreid
  • #5
gsal, thanks. Yes, the algorithm could be made more efficient by eliminating loops. But I do not know whether the running time would be significantly different if you started went from A to B or B to A: that is part of the question (such an algorithm as I am searching for would not exist if there were no difference). That is, I would like to know if there is a difference, and if so, what. It is not obvious that there would be a difference, and it is not obvious that there wouldn't, so I am asking. Anyway, while we are on the question of this algorithm, one thing that strikes me is that the algorithm does not take into account what to do when there are two or more points with the same value assignment and both minimal. That is, what if your algorithm, giving the values to the points, gets to the situation where the algorithm has assigned the values (which are distances to the origin along the paths regarded up to that point) to the neighbors of a current node, and there are two points that fulfill the requirement of being a minimum amongst all the values of all the neighbors? It looks as if it would not be very hard to construct a graph that would make the algorithm freeze in indecision.
 

1. What is Dijkstra's algorithm?

Dijkstra's algorithm is a popular algorithm used in computer science for finding the shortest path between two points in a graph. It takes into account the weight of each edge and finds the most efficient path from the starting point to the destination.

2. How does Dijkstra's algorithm choose the starting point?

Dijkstra's algorithm chooses the starting point based on the weight of the edges connected to it. The algorithm starts at the node with the lowest weight and then explores its neighboring nodes, updating the shortest distance to each node as it goes.

3. What happens if there are multiple starting points in Dijkstra's algorithm?

If there are multiple starting points, the algorithm will explore all of them and update the shortest distance to each node accordingly. However, it will only consider the shortest path from one starting point to the destination, discarding the paths from the other starting points.

4. Can Dijkstra's algorithm be used for graphs with negative edge weights?

No, Dijkstra's algorithm cannot be used for graphs with negative edge weights. The algorithm relies on the assumption that the shortest path to a node is always through the lowest weight edge. If negative edge weights are present, this assumption no longer holds and the algorithm will not produce the correct result.

5. Is Dijkstra's algorithm the most efficient way to find the shortest path in a graph?

Dijkstra's algorithm is considered efficient for finding the shortest path in a graph, but it is not necessarily the most efficient. Other algorithms, such as A* search or Floyd-Warshall algorithm, may be more suitable for certain types of graphs or specific applications. It is important to consider the characteristics of the graph and the specific requirements of the problem before choosing an algorithm.

Similar threads

  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
931
Replies
9
Views
1K
  • Programming and Computer Science
Replies
30
Views
4K
  • Programming and Computer Science
Replies
14
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
29
Views
3K
  • Programming and Computer Science
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
474
Back
Top