Dijkstra’s Algorithm in C++

Yasin Cakal

Dijkstra’s Algorithm is an important algorithm used for solving the path-finding problem in computer science. This algorithm finds the shortest path from a given node to all other nodes in a graph. It is one of the most popular algorithms in computer science and can be used to solve problems in a wide range of fields from robotics to network routing. In this course, Data Structures and Algorithms with C++, we will be discussing the algorithm in detail and its implementation in C++.

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a graph search algorithm that is used to find the shortest path from a given source node to all other nodes in the graph. The algorithm works by first finding the shortest path from the source node to all other nodes in the graph and then using this information to find the shortest path between any two nodes in the graph.

The algorithm works by first selecting a node from the graph and assigning it a distance value of 0. The algorithm then looks at the neighboring nodes and assigns them a distance value based on their distance from the source node. The algorithm then selects the node with the smallest distance value and updates the distance values for its neighbors. This process is repeated until all the nodes in the graph have been visited.

The Algorithm in C++

In this section, we will be discussing the implementation of Dijkstra’s Algorithm in C++. Before we begin, let’s first discuss the data structure we will be using for the implementation. We will be using an adjacency list for this implementation. An adjacency list is an array of linked lists that stores the neighbors of each node. Each node in the list will store the node’s ID, its distance from the source node, and a pointer to its neighbors.

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<pair<int,int> > neighbors; 
};

Now that we have discussed the data structure, let’s look at the code for the Dijkstra’s Algorithm.

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i].first; 
                int weight = graph[u].neighbors[i].second; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + weight) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + weight; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the distance of all the nodes 
    for (int i = 0; i < graph.size(); i++) 
        cout << i << " " << dist[i] << endl; 
}

Time Complexity

The time complexity of Dijkstra’s Algorithm is O(E log V), where E is the number of edges and V is the number of vertices. This makes Dijkstra’s Algorithm one of the most efficient algorithms for finding the shortest path in a graph.

Space Complexity

The space complexity of Dijkstra’s Algorithm is O(V), where V is the number of vertices. This is because the algorithm uses an adjacency list to store the neighbors of each node, which takes up O(V) space.

Conclusion

In this article, we discussed the implementation of Dijkstra’s Algorithm in C++. We discussed the data structure used for the implementation and the code for the algorithm. We also discussed the time and space complexity of the algorithm. As a result, we can conclude that Dijkstra’s Algorithm is an efficient algorithm for finding the shortest path in a graph.

Exercises

Write a program that implements Dijkstra’s Algorithm in C++.

#include <bits/stdc++.h> 

using namespace std; 

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<pair<int,int> > neighbors; 
}; 

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i].first; 
                int weight = graph[u].neighbors[i].second; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + weight) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + weight; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the distance of all the nodes 
    for (int i = 0; i < graph.size(); i++) 
        cout << i << " " << dist[i] << endl; 
} 

int main() 
{ 
    // Initialize the graph 
    vector<Node> graph; 
  
    // Add the nodes to the graph 
    graph.push_back({0, 0, {{1, 3}, {2, 1}}}); 
    graph.push_back({1, INT_MAX, {{3, 4}}}); 
    graph.push_back({2, INT_MAX, {{3, 1}}}); 
    graph.push_back({3, INT_MAX, {}}); 
  
    // Call the dijkstra function 
    dijkstra(graph, 0); 
  
    return 0; 
}

Write a program that finds the shortest path between two given nodes in a graph using Dijkstra’s Algorithm in C++.

#include <bits/stdc++.h> 

using namespace std; 

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<pair<int,int> > neighbors; 
}; 

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source, int dest) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i].first; 
                int weight = graph[u].neighbors[i].second; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + weight) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + weight; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the shortest path from the source to the destination 
    cout << "The shortest path from " << source << " to " << dest << " is " << dist[dest] << endl; 
} 

int main() 
{ 
    // Initialize the graph 
    vector<Node> graph; 
  
    // Add the nodes to the graph 
    graph.push_back({0, 0, {{1, 3}, {2, 1}}}); 
    graph.push_back({1, INT_MAX, {{3, 4}}}); 
    graph.push_back({2, INT_MAX, {{3, 1}}}); 
    graph.push_back({3, INT_MAX, {}}); 
  
    // Call the dijkstra function 
    dijkstra(graph, 0, 3); 
  
    return 0; 
}

Write a program that finds the shortest path between all pairs of nodes in a graph using Dijkstra’s Algorithm in C++.

#include <bits/stdc++.h> 

using namespace std; 

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<pair<int,int> > neighbors; 
}; 

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i].first; 
                int weight = graph[u].neighbors[i].second; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + weight) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + weight; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the shortest path from the source to all other nodes 
    for (int i = 0; i < graph.size(); i++) 
        cout << "Shortest path from " << source << " to " << i << " is " 
             << dist[i] << endl; 
  
    return; 
} 

// Main Function 
int main() 
{ 
    // Create the graph 
    vector<Node> graph; 
  
    // Add the nodes to the graph 
    for (int i = 0; i < 5; i++) 
    { 
        Node temp; 
        temp.id = i; 
        graph.push_back(temp); 
    } 
  
    // Add the edges to the graph 
    graph[0].neighbors.push_back(make_pair(1, 5)); 
    graph[0].neighbors.push_back(make_pair(2, 10)); 
    graph[0].neighbors.push_back(make_pair(3, 8)); 
    graph[1].neighbors.push_back(make_pair(2, 3)); 
    graph[2].neighbors.push_back(make_pair(3, 2)); 
    graph[3].neighbors.push_back(make_pair(4, 4)); 
  
    // Find the shortest path from node 0 to all other nodes 
    dijkstra(graph, 0); 
  
    return 0; 
}

Write a program to find the shortest path from a given source vertex to all vertices in a unweighted graph using Dijkstra’s Algorithm in C++.

#include <bits/stdc++.h> 

using namespace std; 

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<int> neighbors; 
}; 

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i]; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + 1) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + 1; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the shortest path from the source to all other nodes 
    for (int i = 0; i < graph.size(); i++) 
        cout << "Shortest path from " << source << " to " << i << " is " 
             << dist[i] << endl; 
  
    return; 
} 

// Main Function 
int main() 
{ 
    // Create the graph 
    vector<Node> graph; 
  
    // Add the nodes to the graph 
    for (int i = 0; i < 5; i++) 
    { 
        Node temp; 
        temp.id = i; 
        graph.push_back(temp); 
    } 
  
    // Add the edges to the graph 
    graph[0].neighbors.push_back(1); 
    graph[0].neighbors.push_back(2); 
    graph[0].neighbors.push_back(3); 
    graph[1].neighbors.push_back(2); 
    graph[2].neighbors.push_back(3); 
    graph[3].neighbors.push_back(4); 
  
    // Find the shortest path from node 0 to all other nodes 
    dijkstra(graph, 0); 
  
    return 0; 
}

Write a program to find the shortest path from a given source vertex to all vertices in a weighted graph with negative weights using Dijkstra’s Algorithm in C++.

#include <bits/stdc++.h> 

using namespace std; 

// The adjacency list data structure 
struct Node 
{ 
    int id; 
    int dist; 
    vector<pair<int,int> > neighbors; 
}; 

// The function for Dijkstra’s Algorithm 
void dijkstra(vector<Node> &graph, int source) 
{ 
    // Initialize the distance of all nodes to infinity 
    vector<int> dist(graph.size(), INT_MAX); 
  
    // Create a set to store the nodes that have been visited 
    set<pair<int, int> > visited; 
  
    // Set the distance of the source node to 0 
    dist[source] = 0; 
  
    // Create a priority queue to store the nodes in order of their distance 
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; 
  
    // Push the source node in the priority queue 
    pq.push(make_pair(dist[source], source)); 
  
    // While the priority queue is not empty 
    while (!pq.empty()) 
    { 
        // Get the node with the minimum distance 
        int u = pq.top().second; 
        pq.pop(); 
  
        // If the node has not been visited 
        if (visited.find(make_pair(dist[u], u)) == visited.end()) 
        { 
            // Mark it as visited 
            visited.insert(make_pair(dist[u], u)); 
  
            // Update the distance of its neighbors 
            for (int i = 0; i < graph[u].neighbors.size(); i++) 
            { 
                int v = graph[u].neighbors[i].first; 
                int weight = graph[u].neighbors[i].second; 
  
                // If the distance of the neighbor is more than the distance of the source node + the edge weight 
                if (dist[v] > dist[u] + weight) 
                { 
                    // Update the distance of the neighbor 
                    dist[v] = dist[u] + weight; 
  
                    // Push the neighbor in the priority queue 
                    pq.push(make_pair(dist[v], v)); 
                } 
            } 
        } 
    } 
  
    // Print the shortest path from the source to all other nodes 
    for (int i = 0; i < graph.size(); i++) 
        cout << "Shortest path from " << source << " to " << i << " is " 
             << dist[i] << endl; 
  
    return; 
} 

// Main Function 
int main() 
{ 
    // Create the graph 
    vector<Node> graph; 
  
    // Add the nodes to the graph 
    for (int i = 0; i < 5; i++) 
    { 
        Node temp; 
        temp.id = i; 
        graph.push_back(temp); 
    } 
  
    // Add the edges to the graph 
    graph[0].neighbors.push_back(make_pair(1, -5)); 
    graph[0].neighbors.push_back(make_pair(2, -10)); 
    graph[0].neighbors.push_back(make_pair(3, -8)); 
    graph[1].neighbors.push_back(make_pair(2, -3)); 
    graph[2].neighbors.push_back(make_pair(3, -2)); 
    graph[3].neighbors.push_back(make_pair(4, -4)); 
  
    // Find the shortest path from node 0 to all other nodes 
    dijkstra(graph, 0); 
  
    return 0; 
}

Data Structures and Algorithms with C++

Participants 445