Find the shorted path from the vertex 0 for given list of vertices.
Question
For input (separated by a tab) from this link, compute the shortest path from a vertex, 0 to the following vertices.
The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row "141,8200" indicates that there is an edge between vertex 6 and vertex 141 that has a length of 8200. The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges.
Report the shortest path in the same order of given vertices
vertices = [7,37,59,82,99,115,133,165,188,197]
if you find that all ten of these vertices except 115 are at a distance of 1000 away from vertex 1 and 115 is 2000 distances away, then your answer should be
[1000,1000,1000,1000,1000,2000,1000,1000,1000,1000].
Answer
Given the vast number of vertices and edges along with the length value for each edge, using the Dijkstra shortest path algorithm is the best way to solve the problem.
This is the rough algorithm of the Dijkstra shortest path algorithm:
To find the shortest path from S to E.
X = []
V = [ all verties]
A[i]: Dijkstra score for $vertiex_{i}$.
while X != V:
for the edges {v, w} where v $\in$ X and w $\notin$ X
choose the edge whose A[w] is minum of all, where A[w] = A[v] + edge weight of {v, w}
return A[E]
A brute-force implementation of this algorithm run in $O(MN)$.
However, we can do better by using Min heap. This gives will accelerate finding the vertex with a minimum Dijkstra store.
With the Min heap the algorithm will change as below:
X = []
V = [ all verties]
A[i]: Dijkstra score for $ vertex_{i} $.
Pre calculate the Dijkstra scores for all vertices reachable from $V_{1}$ in A[w] while setting the A[i] for the unreachable vertex into MAX_VALUE.
heap = MinHeap()
Add all vertices except for $V_{1}$ to heap
while X != V:
next_node = heap.extract() # extract the vertex with the smallest Dijkstra score
for each edge {v, w} of next_node where v $\in$ X and w $\notin$ X
# delete the w from heap
heap.delete(w)
# calculate the Dijstra score for w
A[w] = A[next_node] + edge weight
heap.add(w)
return A[E]
One thing to keep in mind is that this algorithm requires the new operation for MinHeap, delete(), which allows the extract in the middle of the tree.
This will require the MinHeap to keep track of the position of each element in the array through the separate data structure (e.g. hashtable).
Once the position of an element to be deleted is found, say at K th position, we can perform the bubble_down(K).
The running time of the enhanced algorithm is O(M log N).
Here is the code in python:
Comments
Post a Comment