---
# System prepended metadata

title: Basic Djikstra Algorithm with Adjacency List Implementation and Backtracking
tags: [DSA]

---

# Basic Djikstra Algorithm with Adjacency List Implementation and Backtracking

## Idea and Pseudocode

1. for each vertex v:
&nbsp;&nbsp;&nbsp; dist[v] = infinity
&nbsp;&nbsp;&nbsp; prev[v] = none
2. dist[source] = 0
3. set all vertices to unexplored ~ start empty max/min heap
4. while destination is not explored (max/min heap is not empty):
&nbsp;&nbsp;&nbsp; v = least-valued unexplored vertex (auto implement if using heap)
&nbsp;&nbsp;&nbsp; set v to explored (heap pop)
&nbsp;&nbsp;&nbsp; for each edge connected with v:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Check **if** the dist[v] (*cumulative*) + edge's weight < dist[w] (*saved distance*)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;true then update the saved distance ==dist[w] = dist[v] + edge's weight==
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update the shortest origin ==prev[w] = v==

## Guarantee

Dijkstra's algorithm has a few key guarantees:

1. **Shortest Path**: It guarantees to find the shortest path from a given source node to all other nodes in a graph with non-negative edge weights. The shortest path between two nodes is the path with the minimum total weight (or cost).

2. **Optimality**: Dijkstra's algorithm is optimal, meaning that it will always find the best solution if one exists. This is due to the principle of optimality, which states that every subpath of an optimal path is also optimal.

3. **Non-Negative Weights**: The algorithm assumes that all edge weights are non-negative. This is a critical assumption because if there are negative weights, the algorithm might not provide the correct shortest path.

4. **Time Complexity**: The time complexity of Dijkstra's algorithm is $$O((V+E) \log V)$$ when implemented with a binary heap, where `V` is the number of vertices and `E` is the number of edges in the graph. This makes it efficient for sparse graphs.

Remember, Dijkstra's algorithm does not work correctly with graphs containing edges with negative weights. For graphs with negative weights, algorithms like Bellman-Ford or Johnson’s algorithm can be used. 

## Implementation

```cpp=
#include <bits/stdc++.h>
// The above library is used to generate infinite numbers representation

/**
 * Use typedef to aliase predefined data type example:
 *   typedef vector<int> vInt
 *   vInt vec1 = {1,2}
 * 
 * map is used to store pair of key and value. key is unique
 * map offers find() method to access, also indexing operator map[key]
 * 
 * pair is only used for creating a tuple that holds exactly TWO ITEMS first and second
**/

using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> pair_int;

class Graph {
    public:
        // Custom default constructor for init the graph with number of vertex
        Graph(int num_vertex);
        // Function to add weighted edge to graph
        void addEdge(int u, int v, int w);
        // Function to print the shortest path from a vertex source to all vertices
        void djikstraPrint(int source);
    private:
        int _num_vertex;
        // You can use index operation with stl list
        list<pair_int>* adjList;
};

Graph::Graph(int num_vertex) {
    _num_vertex = num_vertex;
    // Reserve list to connected vertices for each vertex
    adjList = new list<pair_int>[num_vertex];
}

void Graph::addEdge(int u, int v, int w) {
    // Depend on directed or undirectected, if undirected then add the corresponding
    adjList[u].push_back(make_pair(v, w));
    // adjList[v].push_back(make_pair(u, w));
}

void printPath(int currentVertex, vector<int> parents) {
    // Recursive backtracking
    if(parents[currentVertex]!= -1) {
        printPath(parents[currentVertex], parents);
    }
    cout << currentVertex << " -> ";

    /**
      * Visualization of the backtracking:
        printPath(4, parents)
        |__ printPath(2, parents)
            |__ printPath(1, parents)
                |__ printPath(0, parents)  // Base case: prints "0 -> "
            |__ prints "1 -> "
        |__ prints "2 -> "
        |__ prints "4 -> "
    **/
}

void Graph::djikstraPrint(int source) {
    // Create this data structure so that we can easily access and sort the vertex
    priority_queue<pair_int, vector<pair_int>, greater<pair_int>> max_heap;
    // Init storage to store distances with infinity distance for each vertex
    vector<int> counted_distances(_num_vertex, INF);
    // Init storage to backtrack parents
    vector<int> parents(_num_vertex);

    // Start from source
    max_heap.push(make_pair(0, source));
    counted_distances[source] = 0;
    parents[source] = -1;

    // Iterate until the queue is empty, get all the distances
    while(!max_heap.empty()) {
        // Get the new vertex to explore as current vertex
        int currentVertex = max_heap.top().second;
        max_heap.pop();

        // Explore connected vertices in the current vertex
        for(auto& i: adjList[currentVertex]) {
            // Get the connected vertex and its distance/weight
            int connTo = i.first;
            int weight = i.second;

            // Check if there is new shortest path (cumulative + new edge)
            if(counted_distances[currentVertex] + weight < counted_distances[connTo]) {
                // Update the new shortest path
                counted_distances[connTo] = counted_distances[currentVertex] + weight;
                // Push the new shortest path to the queue
                max_heap.push(make_pair(counted_distances[connTo], connTo));
                // Update the new parent
                parents[connTo] = currentVertex;
            }
        }
    }

    cout << "# Backtracking: ";
    for(auto& p : parents) {
        cout << p << " ";
    }
    cout << endl << endl;

    cout << "# Vertices distance from source vertex:\n\n";
    for(int i = 0; i < _num_vertex; i++) {
        cout << "V. " << i << "\t: " << counted_distances[i] << "\n";
        cout << "-Path\t: ";
        printPath(i, parents);
        cout << "Finish!" << endl << endl;
    }
}

int main() {
    int V = 7;
    Graph g(V);

    // making above shown graph
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 6);
    g.addEdge(1, 3, 5);
    g.addEdge(2, 3, 8);
    g.addEdge(3, 4, 10);
    g.addEdge(3, 5, 15);
    g.addEdge(4, 6, 2);
    g.addEdge(5, 6, 6);
    g.djikstraPrint(0);

    return 0;
}

/*
 * RESULT:
# Backtracking: -1 0 0 1 3 3 4 

# Vertices distance from source vertex:

V. 0    : 0
-Path   : 0 -> Finish!

V. 1    : 2
-Path   : 0 -> 1 -> Finish!

V. 2    : 6
-Path   : 0 -> 2 -> Finish!

V. 3    : 7
-Path   : 0 -> 1 -> 3 -> Finish!

V. 4    : 17
-Path   : 0 -> 1 -> 3 -> 4 -> Finish!

V. 5    : 22
-Path   : 0 -> 1 -> 3 -> 5 -> Finish!

V. 6    : 19
-Path   : 0 -> 1 -> 3 -> 4 -> 6 -> Finish!
 
*/
```