How do you implement single source all destination of a weighted graph using c plus plus?

Answer 1

To implement a single source all destination shortest path algorithm for a weighted graph in C++, you can use Dijkstra's algorithm. First, represent the graph using an adjacency list or matrix. Then, initialize a priority queue to efficiently retrieve the vertex with the smallest distance, a distance array to track the shortest distances from the source, and a set to track visited vertices. Iterate through the vertexes, updating the distances of adjacent vertices, until all reachable vertices are processed. Here's a simple code snippet outline:

#include <vector>
#include <queue>
#include <utility> // for std::pair

void dijkstra(int source, const std::vector<std::vector<std::pair<int, int>>& graph) {
    std::vector<int> dist(graph.size(), INT_MAX);
    dist[source] = 0;
    using pii = std::pair<int, int>; // (distance, vertex)
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (const auto& edge : graph[u]) {
            int v = edge.first, weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

In this code, graph is an adjacency list where each entry contains pairs of neighboring vertices and their weights.