How does Djikstra's Algorithm handle cornering?
Consider this graph
If we consider A to be the source node and C to be the destination, Dijkstra’s algorithm will first move to D as it is the shorter path and then begin looking for nodes connecting to D.
Now consider the same graph but without edges from D to B and from D to E.
When the current node is A (initial state), The algorithm finds that the shorter path between B and D is D, So it moves to D. However, now that there are no edges remaining from D and A is already explored, Wouldn't the algorithm get stuck at D. Wouldn't it be better if we decided to move to be B instead of D while at A?
How does the algorithm handle this situation? Thanks
The algorithm is not physically moving in the graph. It's enqueuing nodes that it sees into a priority queue. This allows it to "jump" around arbitrarily, to whichever node has the next shortest path.
- DirectoryInfo.EnumerateFiles(...) causes UnauthorizedAccessException (and other exceptions)
- How can I find the number of concordant/discordant pairs for a given cell in Google Sheets?
- How to sort with incomplete ordering?
- Fast CRC algorithm?
- Extract the closest two numbers that multiply to create a given number
- Best algorithm for delete duplicates in array of strings
- Isn't there any more efficient solution for the CodeForces 919-B/Perfect Number question?
- Understanding the Time Complexity Difference of Two Ways to Generate Subsets
- Online algorithm for calculating standard deviation of counts
- Calculate Time Remaining
- Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
- Search Algorithm to find the k lowest values in a list (selection algorithm/problem)
- While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?
- How to store items in the LIFO stack in a cache-friendly manner?
- What is the time complexity of heapq.nlargest?
- Shell Sort not Swapping Elements Correctly
- Linear time algorithm for computing radius of membership hyper-sphere
- How can I check Hamming Weight without converting to binary?
- Efficient Merge sort implementation in python
- algorithm to detect pools of 0s in a matrix
- how can i make my sklearn prediction model better?
- Is O(log n) always faster than O(n)
- How can I build a directory tree from a list of paths?
- Word Hunt DFS Algorithm Not Finding Optimal Solution
- How to get the first value greater than x in a range with segment tree
- graph algorithm question
- How to find all simple paths of no more than k lengths starting at a vertex in a directed graph?
- Understanding Disk Reads and Cache Misses for B-tree and BST Queries
- Find longest substring without repeating characters
- Minimize repetitions by removing all occurrences of one number