CPSC Notes

Dijkstra's

4 min read

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. Dijkstra’s is guaranteed to find the shortest path in between two nodes in a weighted graph with no negative weights.

Variations

  • Can be used on weighted vs unweighted graphs.
  • Can be used on both cyclic and acyclic graphs.

Idea

The idea behind Dijkstra’s algorithm is to keep track of the current smallest known distance from a source node to every other node in the graph. To do so, we usually use an array or vector called dist to keep track where dist[u] is the shortest known distance from the source node to the node u.

Then, for every node in the graph, we look at each edge and check if there are any other paths leading to that node that are shorter. Because all edge weights are non-negative, once a shortest path to a node is found, no alternative paths can be shorter.

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? 
	
	// set all vertices to have infinite distance to source
	// and an undefined parent node
	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)
			//alternative distance from source node to all the possible edges
			alt = dist[u] + Graph.edge(u, v)
			// if the alternative path is smaller than current tracked
			if alt < dist[v]
				// set the prev to the current prev node
				// and set that distance as current smallest path
				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.

C++ Implementation

vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int src) {
 
    int numberOfVertices = adj.size();
 
    // Min-heap (priority queue) storing pairs of (distance, node)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
	// Initialize all distances to int_max or infinity
    vector<int> dist(numberOfVertices, INT_MAX);
 
 
    // Distance from source to itself is 0
    dist[src] = 0;
    pq.emplace(0, src);
 
    // Process the queue until all reachable vertices are finalized
    while (!pq.empty()) {
    
	    // Grab the top element, i.e., consider the shortest known path
        auto top = pq.top();
        pq.pop();
 
        int distance = top.first;  
        int node = top.second; 
 
        // If this distance not the latest shortest one, skip it
        if (distance > dist[node])
            continue;
 
        // Explore all neighbors of the current node
        for (auto &p : adj[node]) {
            int vertex = p.first; 
            int weight = p.second; 
 
            // If we found a shorter path to v through u, update it
            if (dist[node] + weight < dist[vertex]) {
                dist[vertex] = dist[node] + weight;   
                pq.emplace(dist[vertex], vertex);
            }
        }
    }
 
    // Return the final shortest distances from the source
    return dist;
}

Data Structures

Dijkstra’s requires:

  • Priority queue/minheap
  • Indexed heap

And the total look up cost is

Graph View

Backlinks