Dijkstra Algorithm In C++: Manfred's Implementation
Dijkstra's Algorithm is a cornerstone of graph theory and computer science, used to find the shortest paths between nodes in a graph. In this article, we'll delve into a C++ implementation of Dijkstra's Algorithm, inspired by Manfred's work, providing a comprehensive guide suitable for both beginners and experienced programmers. We'll break down the code step by step, explaining the underlying concepts and how they translate into efficient C++ code.
Understanding Dijkstra's Algorithm
At its core, Dijkstra's Algorithm is a greedy algorithm that iteratively explores the graph, maintaining a set of visited nodes and a priority queue of unvisited nodes. The priority queue is ordered by the current shortest distance from the starting node. The algorithm repeatedly selects the node with the smallest distance, marks it as visited, and updates the distances to its neighbors. This process continues until the destination node is reached or all reachable nodes have been visited.
The key to Dijkstra's Algorithm's efficiency is the use of a priority queue, which allows us to quickly select the node with the smallest distance. This greedy approach guarantees that we find the shortest path, as we always explore the most promising nodes first.
Key Concepts
- Graph Representation: Understanding how graphs are represented in code is crucial. Common methods include adjacency matrices and adjacency lists. In this implementation, we use an adjacency list, which is efficient for sparse graphs (graphs with relatively few edges).
- Adjacency List: An adjacency list represents a graph as a collection of lists, one for each vertex. Each list contains the neighbors of that vertex, along with the cost (weight) of the edge connecting them.
- Priority Queue: A priority queue is a data structure that allows us to efficiently retrieve the element with the highest (or lowest) priority. In Dijkstra's Algorithm, we use a min-priority queue to store nodes based on their distance from the starting node.
- Distance Initialization: Initially, all nodes are assigned an infinite distance, except for the starting node, which has a distance of 0. This ensures that the algorithm correctly explores the graph, updating distances as shorter paths are discovered.
- Relaxation: The relaxation step is the heart of Dijkstra's Algorithm. For each neighbor of the current node, we check if the distance to that neighbor can be shortened by going through the current node. If so, we update the distance and add the neighbor to the priority queue.
C++ Implementation: A Detailed Walkthrough
Let's dive into the C++ code, breaking it down into manageable parts and explaining each section in detail. This implementation showcases the core concepts of Dijkstra's Algorithm in a clear and concise manner.
1. Header Files and Namespace
#include <iostream>
#include <list>
#include <queue>
#define INFINITO 10000000
using namespace std;
We start by including the necessary header files: <iostream> for input/output operations, <list> for representing the adjacency lists, and <queue> for the priority queue. We also define INFINITO as a large number to represent infinite distance and use the std namespace for convenience.
2. The Grafo Class
class Grafo
{
private:
int V; // número de vértices
// ponteiro para um array contendo as listas de adjacências
list<pair<int, int> > * adj;
public:
// construtor
Grafo(int V)
{
this->V = V; // atribui o número de vértices
/*
cria as listas onde cada lista é uma lista de pairs
where each pair is formed by the destination vertex and the cost
*/
adj = new list<pair<int, int> >[V];
}
// adds an edge to the graph from v1 to v2
void addAresta(int v1, int v2, int custo)
{
adj[v1].push_back(make_pair(v2, custo));
adj[v2].push_back(make_pair(v1, custo)); // undirected graph
}
This section defines the Grafo class, which represents the graph. It includes the number of vertices (V) and an array of adjacency lists (adj). The constructor initializes the graph with the given number of vertices, and the addAresta function adds an edge between two vertices with a specified cost. Note that this implementation assumes an undirected graph, so edges are added in both directions.
Adjacency List Explanation
The adj member is a pointer to an array of lists. Each list represents the neighbors of a vertex. The pair<int, int> data type is used to store the destination vertex and the cost of the edge.
For example, adj[0] might contain a list like {(1, 4), (2, 2)}, indicating that vertex 0 has edges to vertex 1 with cost 4 and to vertex 2 with cost 2.
3. Dijkstra's Algorithm Implementation
int dijkstra(int orig, int dest)
{
// distance vector
int dist[V];
/*
visited vector serves in case the vertex has already been
expanded (visited), do not expand anymore
*/
int visitados[V];
int pai[V]; // vector to store the path
// initializes the distance and visited vectors
for(int i = 0; i < V; i++)
{
dist[i] = INFINITO;
visitados[i] = false;
pai[i] = -1; // initializing without parent
}
// the distance from orig to orig is 0
dist[orig] = 0;
// insert into the queue
priority_queue < pair<int, int>,vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push(make_pair(dist[orig], orig));
// algorithm loop
while(!pq.empty())
{
pair<int, int> p = pq.top(); // extracts the pair from the top
int u = p.second; // gets the vertex from the pair
pq.pop(); // removes from the queue
// checks if the vertex has not been expanded
if(visitados[u] == false)
{
// mark as visited
visitados[u] = true;
list<pair<int, int> >::iterator it;
// traverses the adjacent vertices "v" of "u"
for(it = adj[u].begin(); it != adj[u].end(); it++)
{
// gets the adjacent vertex and the edge cost
int v = it->first;
int custo_aresta = it->second;
// relaxation (u, v)
if(dist[v] > (dist[u] + custo_aresta))
{
// updates the distance of "v" and inserts into the queue
dist[v] = dist[u] + custo_aresta;
pai[v] = u; // saves the path
pq.push(make_pair(dist[v], v));
}
}
}
}
This is the core of the algorithm. The dijkstra function takes the origin and destination vertices as input and returns the shortest distance between them. It initializes the dist array with infinite distances, the visitados array with false (not visited), and the pai array with -1 (no parent). The distance from the origin to itself is set to 0.
Priority Queue
A priority queue pq is used to store vertices based on their distances. The greater<pair<int, int> > template argument ensures that the queue is a min-priority queue, meaning the element with the smallest distance is at the top.
Main Loop
The while loop continues as long as the priority queue is not empty. In each iteration, the vertex with the smallest distance is extracted from the queue. If the vertex has not been visited, it is marked as visited, and its neighbors are processed. This ensures Dijkstra's Algorithm only check each vertex a single time.
Relaxation Step
For each neighbor v of the current vertex u, the relaxation step checks if the distance to v can be shortened by going through u. If dist[v] > (dist[u] + custo_aresta), the distance to v is updated, the parent of v is set to u, and v is added to the priority queue.
4. Path Reconstruction and Output
// prints the path
list<int> caminho;
int atual = dest;
while(atual != -1)
{
caminho.push_front(atual);
atual = pai[atual];
}
cout << "Caminho (numeros): ";
for(int v : caminho){
cout << v << " ";}
cout << endl;
char letras[] = { 'A','B','C','D','E','F','G','H','I','J'};
cout << "Caminho (letras): " ;
for (int v : caminho){
cout << letras[v] << " ";}
cout << endl;
// returns the minimum distance to the destination
return dist[dest];
}
};
After the main loop completes, the shortest distance from the origin to the destination is stored in dist[dest]. This section reconstructs the shortest path by tracing back from the destination to the origin using the pai array. The path is stored in the caminho list and printed to the console, both as vertex numbers and corresponding letters.
5. Main Function
int main(int argc, char *argv[])
{
Grafo g(6); // here we change according to the edges being requested//
g.addAresta(0, 1, 4);
g.addAresta(0, 2, 2);
g.addAresta(1, 2, 1);
g.addAresta(1, 3, 5);
g.addAresta(2, 3, 8);
g.addAresta(2, 4, 10);
g.addAresta(3, 4, 2);
g.addAresta(3, 5, 6);
g.addAresta(4, 5, 2);
cout << g.dijkstra(3, 0) << endl;
return 0;
}
The main function creates a Grafo object with 6 vertices and adds several edges with their respective costs. It then calls the dijkstra function to find the shortest path from vertex 3 to vertex 0 and prints the result.
Putting It All Together
This C++ implementation of Dijkstra's Algorithm provides a solid foundation for understanding and applying this fundamental graph algorithm. By breaking down the code into smaller parts and explaining each section in detail, we've made it accessible to programmers of all levels. Remember, the key to mastering algorithms is not just memorizing code but understanding the underlying concepts and how they translate into efficient solutions.
Conclusion
Dijkstra's Algorithm is a powerful tool for solving shortest path problems in various applications, from network routing to map navigation. This comprehensive guide, inspired by Manfred's work, provides a clear and concise C++ implementation, empowering you to use this algorithm effectively. By understanding the core concepts and the C++ code, you can apply Dijkstra's Algorithm to solve real-world problems and further your knowledge of graph theory and algorithm design.
For further exploration of graph algorithms, consider visiting reputable resources like GeeksforGeeks' Dijkstra's Algorithm page. This will provide you with additional insights and examples to enhance your understanding.
