Erenjaeger said:
In this video the solution is: A→B→D→F
but the paths A→B→D and A→E→D both have a distance of 9, so when you get to D you can either have [B,9] or [E,9] where the first entry is the predecessor and the second entry is the 'cost' on that path so far, or here the distance.
is the solution A→E→D→F also correct or is there some reason that he chose the path A→B→D→F?
Dijkstra's algorithm is a graph search algorithm used to find the shortest path between two nodes in a weighted graph. It was developed by Dutch computer scientist Edsger Dijkstra in 1956.
The algorithm works by maintaining a list of unvisited nodes and their distances from the starting node. Then, it iteratively selects the node with the smallest distance and updates the distances of its neighboring nodes. This process continues until the shortest path to the target node is found.
The time complexity of Dijkstra's algorithm is O(|E| + |V|log|V|), where E is the number of edges and V is the number of vertices in the graph. This is because the algorithm uses a priority queue to select the next node with the smallest distance, which has a time complexity of O(log|V|).
No, Dijkstra's algorithm cannot handle negative edge weights. This is because the algorithm relies on the assumption that the shortest path is composed of edges with non-negative weights. If there are negative edge weights, the algorithm may produce incorrect results.
Dijkstra's algorithm has various applications in network routing, transportation planning, and GPS navigation. It is also commonly used in computer science for pathfinding in video games and search algorithms in artificial intelligence.