Question

# Problem Description

Given a directed graph G = (V,E) with edge length l(e) > 0 for any e in E, and a source vertex s. Use Dijkstra’s algorithm to calculate distance(s,v) for all of the vertices v in V.

(You can implement your own priority queue or use the build-in function for C++/Python)

# Input

The graph has `n` vertices and `m` edges.

There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <= s <=n), describing the number of vertices, the number of edges and the source vertex. Each of the following lines contains three integers `a`, `b` and `c`, meaning there is an edge (a,b) belong to E and the length of the edge is c. All the numbers in a line are separated by space. (`1 <= a,b <= n`)

You can assume that 1 <= n <= 1000, 1 <= m <= 5000, and the length of edge is in the range of [1, 1000].

Your code should read the input from standard input (e.g.

using functions `input()/raw_input()` in Python and `cin/scanf` in C++).

# Output

N lines, the i-th line contain a number representing the distance(s,i). If s can not reach the i-th vertex, output `-1` at the i-th line.

Your code should write the output to standard output (e.g. using functions `print` in Python and `cout/printf` in C++).

Answer 1

// C++ implementation for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
#define INF 0x3f3f3f3f 

// iPair ==> Integer Pair 
typedef pair<int, int> iPair; 

// This class represents a directed graph using 
// adjacency list representation 
class Graph { 
        int V; // No. of vertices 

        // In a weighted graph, we need to store vertex 
        // and weight pair for every edge 
        list<pair<int, int> >* adj; 

public: 
        Graph(int V); // Constructor 

        // function to add an reverse edge to graph 
        void addEdgeRev(int u, int v, int w); 

        // prints shortest distance from all 
        // vertex to the given destination vertex 
        void shortestPath(int s); 
}; 

// Allocates memory for adjacency list 
Graph::Graph(int V) 
{ 
        this->V = V; 
        adj = new list<iPair>[V]; 
} 

void Graph::addEdgeRev(int u, int v, int w) 
{ 

        adj[v].push_back(make_pair(u, w)); 
} 

// Prints shortest distance from all vertex to 
// the given destination vertex 
void Graph::shortestPath(int dest) 
{ 
        // Create a priority queue to store vertices that 
        // are being preprocessed. This is weird syntax in C++. 
        // Refer below link for details of this syntax 
        // https:// www.geeksforgeeks.org/implement-min-heap-using-stl/ 
        priority_queue<iPair, vector<iPair>, greater<iPair> > pq; 

        // Create a vector for distances and initialize all 
        // distances as infinite (INF) 
        vector<int> dist(V, INF); 

        // Insert destination itself in priority queue and initialize 
        // its distance as 0. 
        pq.push(make_pair(0, dest)); 
        dist[dest] = 0; 

        /* Looping till priority queue becomes empty (or all 
        distances are not finalized) */
        while (!pq.empty()) { 

                // The first vertex in pair is the minimum distance 
                // vertex, extract it from priority queue. 
                // vertex label is stored in second of pair (it 
                // has to be done this way to keep the vertices 
                // sorted distance (distance must be first item 
                // in pair) 
                int u = pq.top().second; 
                pq.pop(); 

                // 'i' is used to get all adjacent vertices of a vertex 
                list<pair<int, int> >::iterator i; 
                for (i = adj[u].begin(); i != adj[u].end(); ++i) { 

                        // Get vertex label and weight of current adjacent 
                        // of u. 
                        int v = (*i).first; 
                        int weight = (*i).second; 

                        // If there is shorted path to v through u. 
                        if (dist[v] > dist[u] + weight) { 
                                // Updating distance of v 
                                dist[v] = dist[u] + weight; 
                                pq.push(make_pair(dist[v], v)); 
                        } 
                } 
        } 

        // Print shortest distances stored in dist[] 
        printf("Destination Vertex Distance "
                "from all vertex\n"); 
        for (int i = 0; i < V; ++i) 
                printf("%d \t\t %d\n", i, dist[i]); 
} 

// Driver program to test methods of graph class 
int main() 
{ 
        // create the graph given in above figure 
        int V = 5; 
        Graph g(V); 

        // adding edges in reverse direction 
        g.addEdgeRev(0, 2, 1); 
        g.addEdgeRev(0, 4, 5); 
        g.addEdgeRev(1, 4, 1); 
        g.addEdgeRev(2, 0, 10); 
        g.addEdgeRev(2, 3, 5); 
        g.addEdgeRev(3, 1, 1); 
        g.addEdgeRev(4, 0, 5); 
        g.addEdgeRev(4, 2, 100); 
        g.addEdgeRev(4, 3, 5); 

        g.shortestPath(0); 

        return 0; 
}