Knowledge Base | Daily Notes

Dijkastras

Aug 30, 20243 min read

  • It was designed by Dutch physicist Edsger Dijkstra in 1956, when he thought about how he might calculate the shortest route from Rotterdam to Groningen. Given a graph and a source vertex in the graph, find the shortest paths from source to all vertices in the given graph.
    Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate an SPTShortest_Path_Tree with a given source as root. We maintain two sets, one set contains vertices included in the shortest-path tree, another set includes vertices not yet included in the shortest-path tree. At every step of the algorithm, we find a vertex that is in the other set (set of not yet included) and has a minimum distance from the source.

  • Time complexity: E log V

Approach:

  • Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.
    This is required for Minimum Cost Path

  • Algo needs graph and source from which shortest distance for all nodes have to be calculated

  • Create two array of size, number of vertex.

  • the first array contains distance and will be initialized with infinite values.

  • in js infinite = Number.MAX_VALUE

  • spt set should be initialised with false.

  • handle case of source having distance with itself as 0

  • sptSet contains Boolean value that distance is min or not

  • Keep going node to node picking the minimum values from every node

  • minDistance → take distance and is min distance array and return index of min element

  • mark the is min distance of above node true.

  • Update dist[v] only if is not in

          // sptSet, there is an edge from u 

      // to v, and total weight of path 

      // from src to v through u is smaller 

      // than current value of dist[v] 

import heapq
 
# iPair ==> Integer Pair
iPair = tuple
 
# This class represents a directed graph using
# adjacency list representation
class Graph:
	def __init__(self, V: int): # Constructor
		self.V = V
		self.adj = [[] for _ in range(V)]
 
	def addEdge(self, u: int, v: int, w: int):
		self.adj[u].append((v, w))
		self.adj[v].append((u, w))
 
	# Prints shortest paths from src to all other vertices
	def shortestPath(self, src: int):
		# Create a priority queue to store vertices that
		# are being preprocessed
		pq = []
		heapq.heappush(pq, (0, src))
 
		# Create a vector for distances and initialize all
		# distances as infinite (INF)
		dist = [float('inf')] * self.V
		dist[src] = 0
 
		while pq:
			# The first vertex in pair is the minimum distance
			# vertex, extract it from priority queue.
			# vertex label is stored in second of pair
			d, u = heapq.heappop(pq)
 
			# 'i' is used to get all adjacent vertices of a
			# vertex
			for v, weight in self.adj[u]:
				# If there is shorted path to v through u.
				if dist[v] > dist[u] + weight:
					# Updating distance of v
					dist[v] = dist[u] + weight
					heapq.heappush(pq, (dist[v], v))
 
		# Print shortest distances stored in dist[]
		for i in range(self.V):
			print(f"{i} \t\t {dist[i]}")
 
# Driver's code
if __name__ == "__main__":
	# create the graph given in above figure
	V = 9
	g = Graph(V)
 
	# making above shown graph
	g.addEdge(0, 1, 4)
	g.addEdge(0, 7, 8)
	g.addEdge(1, 2, 8)
	g.addEdge(1, 7, 11)
	g.addEdge(2, 3, 7)
	g.addEdge(2, 8, 2)
	g.addEdge(2, 5, 4)
	g.addEdge(3, 4, 9)
	g.addEdge(3, 5, 14)
	g.addEdge(4, 5, 10)
	g.addEdge(5, 6, 2)
	g.addEdge(6, 7, 1)
	g.addEdge(6, 8, 6)
	g.addEdge(7, 8, 7)
 
	g.shortestPath(0)

Output:

Graph View

Backlinks