Djikstra's

Dijkstra’s

Dijkstra’s is a pathfinding algorithm used on graphs. As opposed to other algorithms like BFS, Dijkstra’s takes into account edge weight. It is considered a greedy algorithm.

Variations

• Can be used on weighted vs unweighted graphs.
• Can be used on both cyclic and acyclic graphs.
• Positive weights only vs negative weights allowed (what does this mean? )
• Multiple weight types to optimize

Implementation

TODO

Where dist is an array of distances from they of source vertex to that vertex. Where prev is an array of pointers to the node predecessing the note at that index

Pseudocode

Dijkstra(Graph, source)
 
	PQ  <- PQ/minheap storing vertex priority
	
	dist[source] <- 0 
	PQ.add(source, 0) //add and heapify? 
	
	for each vertex v in Graph.Vertices
		if v != source
			prev[v] = undefined
			dist[v] = infinity
			PQ.add(v, INFINITY)
	
	while PQ != empty
		u = PQ.min //Top of the heap, so would also be PQ[0]
		for each edge e (u, v)
			alt = dist[u] + Graph.edge(u, v)
			if alt < dist[v]
				prev[v] = u
				dist[v] = alt
				PQ.decrease_prio(v, alt)
				
	return (dist, prev)
		

It seems like Dijkstra’s is implemented with a priority queue minheap that locally keeps track of the shortest path from the current vertex to the nearest other vertex.

It also keeps track of a predecessor node for some reason.

Ah it’s because the process of finding a path from one to the other is by building a data structure that contains all nodes with what node is the cheapest to get to that node by. Then, you can backtrack your way from the destination to the start.

Data Structures

Dijkstra’s requires:

• Priority queue/minheap
• Indexed heap

And the total look up cost is

$$O((n+m)\log n)$$