Exploration: Dijkstra’s algorithm
代写Data structure | Algorithm代写 | oop代写 – 本题是一个利用Data structure进行练习的代做, 对Data structure的流程进行训练解析, 是比较有代表性的Data structure/Algorithm/oop等代写方向
Introduction
In this section, we will explore an Algorithm that can be used in applications like Uber, Lyft to find the shortest path from a source to destinations, this is called Dijkstra algorithm. It is a Dutch name, where j is either silent or is pronounced like y. Dijkstra is pronounced as Dyk( as in bike ) -stra.
As you go through this exploration try to answer the following questions:
What is the Dijkstra algorithm and how to implement it?
What are the applications of Dijkstra algorithm?
The Dijkstra Algorithm
Suppose you want to solve a problem to find ‘all food places near me’. Your algorithm should return all the food places and the distance from your location.
####### In the above figure, what is the length of the shortest path from Home to
####### McDonald’s?
8 mi
28 mi
17 mi
24 mi
Check
To solve this problem we can use Dijkstra’s algorithm. Did you notice that the graph is a weighted graph? Dijkstra’s algorithm is used to solve similar problems that have a weighted graph but the weights should be non-negative.
Let us look at the Dijkstra’s algorithm and find the shortest path from node A to all other nodes in the below graph. Let A be the source node and our goal is to find the shortest path to all other nodes from A.
To begin with, let us look at the method to the shortest path from A to B. If we simply use BFS it will return (A–>B). But the actual shortest path is (A–>D–>B). To solve this let us use the algorithm technique that we learnt before, the greedy algorithm, along with BFS.
The general idea is to pick the locally best choice to obtain a globally optimal solution.
Access Denied
The relation that we use to find the local minimum can be written as (consider that we are calculating the distance from node u to node v):
dist[v] = min{ dist[v] , weight[u,v]+dist[u] }
Code Practice
####### Can you write the pseudocode for the algorithm:
Check
Click here to reveal the answer.
####### Explanation
We are setting the initial distance of all nodes to infinity and source node distance to 0.
dist[v] = infinity for all v in V
dist[Source] = 0
Then we are looping through all the unvisited nodes and picking the unvisited node that has the least distance from the source node.
while length(unvisited)> 0 :
currentNode = From unvisited nodes select node u where dist[u] is smallest
Then, we are checking the neighbors of the selected node and calculating the shortest distance using the relation that we discussed above.
for v in currentNode.neighbors:
dist[v] = min {dist[v] , weight(currentNode, v) + dist[currentNode] }
Finally, we have updated the visited node.
To discuss the time complexity of this algorithm we need to decide upon the data structures we want to use in the code. We are repeatedly looking out for the smallest distance node, this sounds like what a priority queue implemented as min-heap can do for us.
If we use the priority queue the pseudocode will be:
def Dijkstra(G,s):
#Add nodes to min-priority queue Q with initial distance infinity
for v in V:
Enqueue(Q, v,'infinity')
#in Q make source priority = 0
DecreaseKey(Q, source, 0 )
visited = []
#while length of Queue is valid
while(length(Q) > 0 ):
currentNode = Dequeue(Q) #pick and delete the min distance node
visited.append(currentNode)
for v in currentNode.neighbours:
dist_V = min{dist_V, weight(currentNode, v) + dist_currentNode}
DecreaseKey(Q, v, dist_V )
####### Time complexity
The while l oop is executed E times for each edge and the inner for loop will be executed V times for each vertex since we are covering each vertex only once. Decrease key and Dequeue takes log V time complexity. Hence, this algorithm will have O((V+E)logV) time complexity.
####### If we implement the Dijkstra algorithm using the naive approach using array
####### Data structure instead of the priority queue, what will be the time complexity
####### of execution?
######## O(V^2 )
######## O(E)
######## O(V+E^2 )
O((V+E)log V)
Check
Correctness Proof
Lemma: For each x VisitedNodes, dist(x) = smallestDistance(x)
dist(x) is the distance calculated by the algorithm, let us represent it as A(x).
smallestdistance(x) is the correct smallest distance from the source node to x, let us represent it as C(x)
Proof by Induction:
Base Case: When |VisitedNodes| = 1, The first node that is visited is the source node(S). C(x) =0, Our algorithm sets the distance from the source node to 0. So, A(x)=C(x).
Inductive Hypothesis: All the k nodes (u, u, … u ) that are already in the VisitedNodes set have the distance calculated A(x)=C(x).
Inductive Step:
We need to show that the next node that is added to VisitedNode set (say w*) has the smallest distance from S.
Let us mark the VisitedNode set by region R
We will prove this by contradiction.
There must exist a path P from S to w* and this path would cross the region R at some point.
The lenght of path P, len(P) = A(u) + len(u,w*)
Assume that there is another node v outside R on path P that gives us the shortest distance from s to w*.
len(P) = A(u) + len(uv) + len(vw*)
A(u) + len(u,w*) = A(u) + len(uv) + len(vw*)
1 2 k
Since dijkstra is for non negative weights. len(vw*) >=
A(u) + len(u,w*) >= A(u) + len(uv)
len(uw*) >= len(uv)
Now, let us invoke the Greedy property used by Dijkstra algorithm.
If there exists a Node v, that has a shorter distance than w, v would have been visited next not w. So, our assumption that there exists a node v on outside region R that has shorter distance than w* is false.
Hence, w* is the next node with shorter distance outside region R.
By our inductive hypothesis, all the nodes inside R have the best shortest distance. A(u) already has the optimal distance calculated.
A(u)+len(uw) will give us optimal distance of w from S.
Limitations of the Dijkstra Algorithm
The Dijkstra algorithm does not work with negative edges.
Exercises
Implement Dijkstra algorithm that is discussed in the exploration. The solution is in
solution.py. Optionally, you can access the solution from the GitHub link
(https://github.com/DURepo/CS_325_Exercises/blob/main/Graph-calculate_distances.py).
Run open in
Console Shell
main.py
'''
Implement a function calculate_distances(graph, starting_vertex)
Example:
example_graph = {
'U': {'V': 2, 'W': 5, 'X': 1},
'V': {'U': 2, 'X': 2, 'W': 3},
1 2 3 4 5 6 7
Optional Additional Resources
Refer to the following resources for additional reading.
Algorithms by Jeff Erickson, Chapter 8, section 8.