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:

	'''
	find the shortest path using Dijkstra shortest path algorithm given the list of vertices and the relationship of (v, w)
	'''
	import os
	import sys
	import json
	def load_file(path):
	f = open(os.path.join(sys.path[0], path), "r")
	return f.readlines()
	MAX_VALUE = 1000000
	# Min heap
	class MinHeap:
	def __init__(self, weight_map):
	self.positions = {}
	self.list = [None]
	self.weight_map = weight_map
	def parent(self, child):
	return child // 2
	def left(self, parent):
	return 2 * parent
	def right(self, parent):
	return 2 * parent + 1
	def swap(self, src, dst):
	src_value = self.list[src].value
	dst_value = self.list[dst].value
	tmp = self.list[src]
	self.list[src] = self.list[dst]
	self.list[dst] = tmp
	# update the position map after swap
	self.positions[dst_value] = src
	self.positions[src_value] = dst
	def len(self):
	return len(self.list) - 1
	def is_child(self, parent, child):
	return self.weight_map[int(self.list[parent].value)] < self.weight_map[int(self.list[child].value)]
	def bubble_up(self, child):
	parent = self.parent(child)
	if parent < 1:
	return
	if self.is_child(parent, child) != True:
	self.swap(parent, child)
	self.bubble_up(parent)
	def bubble_down(self, parent):
	left = self.left(parent)
	if left > self.len():
	return
	right = self.right(parent)
	to_swap = left if right > self.len() or self.is_child(left, right) == True else right
	if self.is_child(parent, to_swap) != True:
	self.swap(parent, to_swap)
	self.bubble_down(to_swap)
	def extract(self):
	if self.len() == 0:
	return None
	value = self.list[1]
	self.swap(1, len(self.list)- 1)
	self.list.pop()
	del self.positions[value.value]
	self.bubble_down(1)
	return value
	def add(self, vertex):
	self.list.append(vertex)
	self.positions[vertex.value] = len(self.list) - 1
	self.bubble_up(len(self.list) - 1)
	def delete(self, target):
	pos = self.positions[int(target)]
	vertex = self.list[pos]
	# move to the end and remove it.
	self.swap(pos, len(self.list) - 1)
	self.list.pop()
	del self.positions[int(target)]
	self.bubble_down(pos)
	return vertex
	# graph data structure
	class Vertex:
	def __init__(self, value):
	self.value = int(value)
	self.edges = []
	def __str__(self):
	value = {
	'value': self.value,
	'edges': [ "{}".format(e) for e in self.edges]
	}
	return json.dumps(value)
	class Edge:
	def __init__(self, value, v, w):
	self.value = int(value)
	self.v = v
	self.w = w
	def __str__(self):
	value = {
	'value': self.value,
	'v': self.v.value,
	'w': self.w.value
	}
	return json.dumps(value)
	class DijkstraShortestPath:
	def __init__(self, input_path):
	self.vertices = {}
	self.build_graphs(input_path)
	def build_graphs(self, path):
	lines = load_file(path)
	for line in lines:
	token = line.split("\t")
	if token[0] not in self.vertices:
	self.vertices[token[0]] = Vertex(token[0])
	v = self.vertices[token[0]]
	for i in range(1, len(token)):
	if token[i] != '\n' and token[i] != '':
	# parse the edge
	info = token[i].split(",")
	if info[0] not in self.vertices:
	self.vertices[info[0]] = Vertex(info[0])
	w = self.vertices[info[0]]
	edge = Edge(info[1], v, w)
	v.edges.append(edge)
	def initialize_shortest_path_list(self):
	self.weights = [MAX_VALUE for i in range(len(self.vertices) + 1)]
	self.weights[1] = 0
	self.weights[0] = 0
	v1 = self.vertices['1']
	# compute the initial Dijkstra score for all vertices reachable from vertex 1
	for edge in v1.edges:
	self.weights[int(edge.w.value)] = self.weights[1] + edge.value
	def calculate_shortest_path(self, target):
	# initialize the weight map
	self.initialize_shortest_path_list()
	# create a min heap
	heap = MinHeap(self.weights)
	X = {1: True} # start with 1
	# add all vertices into heap except for vertex 1
	for k in self.vertices:
	if k != '1':
	heap.add(self.vertices[k])
	while len(X) != len(self.vertices):
	# extract the vertex with the minimal dijkstra score
	next = heap.extract()
	X[next.value] = True
	# recalculate all vertex's dijkstra score
	for e in next.edges:
	# if w is not part of X
	if e.w.value not in X:
	# remove e.w from the heap
	w = heap.delete(e.w.value)
	self.weights[int(w.value)] = self.weights[int(next.value)] + e.value
	heap.add(w)
	if self.weights[target] != MAX_VALUE: # we found the dijstra score for the target.
	return self.weights[target]
	# we searched ever nodes. We might not find it.
	return self.weights[target]
	def find_shortest_path(self, input):
	result = []
	for i in input:
	value = self.calculate_shortest_path(i)
	result.append(value)
	return result
	# test
	finder = DijkstraShortestPath("dijkstra_graph.txt")
	input = [80,37,59,82,99,115,133,165,188,197]
	result = finder.find_shortest_path(input)
	print("shortest path for {} are {}".format(input, result))

view raw dijkstra_shortest_path.py hosted with ❤ by GitHub

Practice statistics:

02:14:25: To write up the working code using the heap. Made critical mistakes in the position tracking logic. Had to spend lots of time debugging due to that.

Post settings Labels Published on 6/21/22 9:12 PM Permalink Location Options Post: Edit