Skip to main content
Clearer explanation.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.


However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

We now need to pick a new current nodecurrent node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.


While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1. 

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new distance-vertex pair into the bigger min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update the shortest distance so far to that vertex. For example, when the new distance is not shorter than the shortest distance so far.)


Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.


However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.


While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1. 

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new distance-vertex pair into the min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update shortest distance so far to that vertex. For example, when the new distance is not shorter than the distance so far.)


Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.


However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.


While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1. 

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new distance-vertex pair into the bigger min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update the shortest distance so far to that vertex. For example, when the new distance is not shorter than the shortest distance so far.)


Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.

Clearer explanation.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Congratulations! You just found ahave discovered an interesting variation of Dijkstra's algorithm.

 

However, it is not correctmisleading to say thatstate the standard version of Dijkstra's algorithm (SDAstDA) as you mentioneddescribed here as mentioned in the question does not use a shortest path first search while your algorithm does. You might have missedoverlooked the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is why I callthe main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.

 

On the other hand, whileWhile the neighbours of each node are checkedselected in no specific order at some moment in SDAstDA, the same procedureunorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1. 
 

Instead of including each vertex exactly once in the "to do"priority queue of unvisited vertex as in SDAstDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than SDAstDA, since the number of operations to insert a new distance-vertex pair into the min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update shortest distance so far to that vertex. For example, when the new distance is not shorter than the distance so far.) 


Instead of the separate relaxation step as in the SDAstDA, your algorithm usecleverly accomplished the heappop to selectobject of the relaxation step in the same step that selects the shortest path to an unvisited vertex, which, in fact, contains that by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm seemsis slightly easier to code than the SDAstDA.

Congratulations! You just found a variation of Dijkstra's algorithm.

However, it is not correct to say that the standard Dijkstra's algorithm (SDA) as you mentioned here does not use a shortest path first search while your algorithm does. You might have missed the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is why I call your algorithm a variation of Dijkstra's algorithm.

On the other hand, while the neighbours of each node are checked in no specific order at some moment in SDA, the same procedure is done in your algorithm in the following lines

for v2, v1_to_v2_dist in graph[v1].items():
  # code to record the distance to v2 via v1. 

Instead of including each vertex exactly once in the "to do" queue as in SDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than SDA.) Instead of the relaxation step as in the SDA, your algorithm use the heappop to select the shortest path to an unvisited vertex, which, in fact, contains that relaxation step implicitly.

Overall, your algorithm seems easier to code than the SDA.

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.

 

However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.

 

While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1. 
 

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new distance-vertex pair into the min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update shortest distance so far to that vertex. For example, when the new distance is not shorter than the distance so far.) 


Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.

Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Congratulations! You just found a variation of Dijkstra's algorithm.

However, it is not correct to say that the standard Dijkstra's algorithm (SDA) as you mentioned here does not use a shortest path first search while your algorithm does. You might have missed the following statement in that article

We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is why I call your algorithm a variation of Dijkstra's algorithm.

On the other hand, while the neighbours of each node are checked in no specific order at some moment in SDA, the same procedure is done in your algorithm in the following lines

for v2, v1_to_v2_dist in graph[v1].items():
  # code to record the distance to v2 via v1. 

Instead of including each vertex exactly once in the "to do" queue as in SDA, your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than SDA.) Instead of the relaxation step as in the SDA, your algorithm use the heappop to select the shortest path to an unvisited vertex, which, in fact, contains that relaxation step implicitly.

Overall, your algorithm seems easier to code than the SDA.