Shortest path algorithm

Dijkstra's algorithm

Dijkstra's algorithm is a well-known algorithm for finding the shortest path between two vertices in a graph. Here's an explanation of Dijkstra's algorithm and its implementation in C++.

Explanation: Dijkstra's algorithm works by maintaining a priority queue of nodes to explore next. Starting from the source node, it calculates the minimum distance to each node in the graph by keeping track of the minimum distance it takes to reach that node. The algorithm ensures that the nodes closest to the source node are explored first. Once all the nodes have been visited, the algorithm has found the shortest path from the source node to each node in the graph.

Implementation: Here's an implementation of Dijkstra's algorithm in C++. In this example, we have used an adjacency list to represent the graph.


#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii;

const int INF = INT_MAX;

vector<vector<pii>> graph;

vector<int> dijkstra(int source) {
    vector<int> dist(graph.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push(make_pair(0, source));
    dist[source] = 0;

    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for(auto i : graph[u]) {
            int v = i.first;
            int weight = i.second;

            if(dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);

    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int source;
    cin >> source;

    vector<int> dist = dijkstra(source);

    for(int i = 0; i < n; i++) {
        cout << "Shortest distance from " << source << " to " << i << " is " << dist[i] << "\\n";
    }

    return 0;
}

In this implementation, we have used a typedef to represent an edge as a pair of integers. We have also used the pii to represent a pair of integers.

The dijkstra function takes the source node as input and returns a vector of minimum distances from the source to each node. It implements Dijkstra's algorithm using a priority queue to explore each node in order of increasing distance from the source.

The main function takes input for the number of vertices and edges and the edges' weight between vertices. It uses the dijkstra function to calculate the shortest path from the source node to each node in the graph. Finally, it prints the results to the console.

This implementation is just one way of implementing Dijkstra's algorithm in C++. Different implementations may be better suited for different applications, depending on factors like the size of the graph, the distribution of edge weights, and the desired speed and memory usage.

Prim’s Algorithm:

Prim's algorithm is a commonly used algorithm to find the minimum spanning tree (MST) for a connected weighted graph. Here's an explanation of Prim's algorithm and its implementation in C++.

Explanation: Prim's algorithm works by maintaining a set of edges that form a minimum spanning tree. Starting from an arbitrary vertex, it finds the edge with the minimum weight that connects the tree to a vertex that is not in the tree and adds it to the tree. The algorithm iterates this process until all the vertices are included in the tree.

Implementation: Here's an implementation of Prim's algorithm in C++. In this example, we have used an adjacency list to represent the graph.


#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii;

const int INF = INT_MAX;

vector<vector<pii>> graph;

int prim(int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);

    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push(make_pair(0, start));
    dist[start] = 0;

    int mstWeight = 0;
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if(visited[u]) continue;
        visited[u] = true;
        mstWeight += dist[u];

        for(auto i : graph[u]) {
            int v = i.first;
            int weight = i.second;

            if(dist[v] > weight && !visited[v]) {
                dist[v] = weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    return mstWeight;
}

int main() {
    int n, m;
    cin >> n >> m;

    //filling the graph
    graph.resize(n);
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int start;
    cin >> start;

    int mstWeight = prim(start);

    cout << "Minimum Spanning Tree Weight is " << mstWeight << endl;

    return 0;
}

In this implementation, we have used a typedef to represent an edge as a pair of integers. We have also used the pii to represent a pair of integers.

The prim function takes the start node as input and returns the weight of the minimum spanning tree. It implements Prim's algorithm using a priority queue to explore each node in order of increasing cost.

The main function takes input for the number of vertices and edges and the edges' weight between vertices. It uses the prim function to calculate the minimum spanning tree's weight and prints the result to the console.

This implementation is just one way of implementing Prim's algorithm in C++. Different implementations may be better suited for different applications, depending on factors like the size of the graph, the distribution of edge weights, and the desired speed and memory usage.

Kruskal’s Algorithm:

Kruskal's algorithm is a widely used algorithm that finds a minimum spanning tree (MST) for a connected weighted graph. Here's an explanation of Kruskal's algorithm and its implementation in C++.

Explanation: Kruskal's algorithm works by initially sorting all the edges in the graph based on weight. It then starts from the edge with the lowest weight and includes it in the MST if it doesn't create a cycle. It then proceeds to the next edge with the lowest weight, and so on, until all vertices are connected in the MST.

Implementation: Here's an implementation of Kruskal's algorithm in C++. In this example, we have used an adjacency list to represent the graph.


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

class Edge {
public:
    int u;
    int v;
    int weight;

    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

vector<Edge> edges;
vector<int> parent;

int find(int x) {
    if(parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

int kruskal() {
    int mst = 0;
    int n = parent.size();

    for(int i = 0; i < n; i++) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end());

    for(auto cur : edges) {
        if(find(cur.u) != find(cur.v)) {
            unite(cur.u, cur.v);
            mst += cur.weight;
        }
    }

    return mst;
}

int main() {
    int n, m;
    cin >> n >> m;

    parent.resize(n);

    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int mstWeight = kruskal();

    cout << "Minimum Spanning Tree Weight is " << mstWeight << endl;

    return 0;
}

In this implementation, we have used a typedef to represent an edge as a pair of integers. We have also used the pii to represent a pair of integers. Edge class is taking other integers u, v and weight.

The find function finds the set that a particular vertex belongs to using the Union-Find algorithm.

The unite function combines two sets.

The kruskal function initializes the parent array, sorts the edges list, and uses a loop that adds edges to the MST if they do not create a cycle.

The main function takes input for the number of vertices and edges and the edges' weight between vertices. It uses the kruskal function to calculate the minimum spanning tree's weight and prints the result to the console.

This implementation is just one way of implementing Kruskal's algorithm in C++. Different implementations may be better suited for different applications, depending on factors like the size of the graph, the distribution of edge weights, and the desired speed and memory usage.

Bellman-Ford Algorithm:

Bellman-Ford algorithm is a well-known algorithm in graph theory that finds the shortest path between a source vertex and all other vertices in a graph. It can handle negative edge weights unlike Dijkstra’s algorithm.

Explanation: The Bellman-Ford algorithm works by processing all the edges in the graph until no further improvements can be made. It maintains an array of distances that stores the shortest known distance from the source vertex to each vertex. In each iteration of the algorithm, it relaxes the edges by trying to improve the current shortest distance between a pair of vertices by checking if there is a shorter path between them.

Implementation: Here's an implementation of the Bellman-Ford algorithm in C++. In this example, we have used an adjacency list to represent the graph.


#include <iostream>
#include <vector>
#include <climits>
using namespace std;

typedef pair<int, int> pii;

const int INF = INT_MAX;

vector<vector<pii>> graph;

vector<int> bellmanFord(int start) {
    int n = graph.size();

    vector<int> dist(n, INF);
    dist[start] = 0;

    for(int i = 0; i < n - 1; i++) {
        for(int u = 0; u < n; u++) {
            for(auto v : graph[u]) {
                int adj = v.first;
                int weight = v.second;

                if(dist[u] == INF) continue;

                if(dist[adj] > dist[u] + weight) {
                    dist[adj] = dist[u] + weight;
                }
            }
        }
    }

    // Negative Cycle Check
    for(int u = 0; u < n; u++) {
        for(auto v : graph[u]) {
            int adj = v.first;
            int weight = v.second;
            if(dist[u] != INF && dist[u] + weight < dist[adj]) {
                cout << "Graph contains negative weight cycle";
                return vector<int>();
            }
        }
    }

    return dist;
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);

    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
    }

    int start;
    cin >> start;

    vector<int> dist = bellmanFord(start);

    if(dist.empty()) return 0;

    for(int i = 0; i < n; i++) {
        cout << "Shortest distance from " << start << " to " << i << " is " << dist[i] << "\\n";
    }

    return 0;
}

In this implementation, we have used a typedef to represent an edge as a pair of integers. We have also used the pii to represent a pair of integers.

The bellmanFord function takes the start node as input and returns a vector of minimum distances from the start to each node. It implements the Bellman-Ford algorithm by processing all the edges in the graph and relaxing them.

The main function takes input for the number of vertices and edges and the edges' weight between vertices. It uses the bellmanFord function to calculate the shortest path from the start node to each node in the graph. Finally, it prints the results to the console.

This implementation is just one way of implementing the Bellman-Ford algorithm in C++. Different implementations may be better suited for different applications, depending on factors like the size of the graph, the distribution of edge weights, and the desired speed and memory usage.

PRACTICE PROBLEMS :

Cheapest Flights Within K Stops

Find the City With the Smallest Number of Neighbors at a Threshold Distance