# Basic Djikstra Algorithm with Adjacency List Implementation and Backtracking
## Idea and Pseudocode
1. for each vertex v:
dist[v] = infinity
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):
v = least-valued unexplored vertex (auto implement if using heap)
set v to explored (heap pop)
for each edge connected with v:
Check **if** the dist[v] (*cumulative*) + edge's weight < dist[w] (*saved distance*)
true then update the saved distance ==dist[w] = dist[v] + edge's weight==
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!
*/
```
Sign in with Wallet
Connect another wallet