Dijkstra's shortest path
You have been given an undirected graph of ‘V’ vertices (labelled from 0 to V-1) and ‘E’ edges. Each edge connecting two nodes u and v has a weight denoting the distance between them.

Your task is to find the shortest path distance from the source node (For this problem, it is the node labelled as 0) to all vertices given in the graph.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph. 2. There are no parallel edges i.e no two vertices are directly connected by more than 1 edge. 3. Print the maximum positive integer value, i.e 2147483647, for the disconnected nodes.

For Example:

Input: 4 5 0 1 5 0 2 8 1 2 9 1 3 2 2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5. In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘u’, the second number denotes node ‘v’ and the third number denotes the distance between node ‘u’ and ‘v’. As per the input, there is an edge between node 0 and node 1 and the distance between them is 5. The vertices 0 and 2 have an edge between them and the distance between them is 8. The vertices 1 and 2 have an edge between them and the distance between them is 9. The vertices 1 and 3 have an edge between them and the distance between them is 2. The vertices 2 and 3 have an edge between them and the distance between them is 6.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains two single space-separated integers ‘V’ and ‘E’ denoting the number of vertices and the number of edges in the undirected graph, respectively. The next ‘E’ lines each contain three single space-separated integers ‘u’, ‘v’, and ‘distance’, denoting a node ‘u’, a node ‘v’, and the distance between nodes (u, v) respectively.

Output format:

For each test case, print the shortest path distance from the source node, which is the node labelled as 0, to all vertices given in the graph in ascending order of the node number. Shortest path distance between source node and node labelled as 0 will be printed first followed by the distance between source node and node labelled as 1 and so on to the distance between source node and node labelled as ‘V-1’. Note: You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the answer which is the shortest path distance from the source node (the node labelled as 0) to all vertices given in the graph in ascending order of the node number.

Constraints:

1

Question

Dijkstra's shortest path

You have been given an undirected graph of ‘V’ vertices (labelled from 0 to V-1) and ‘E’ edges. Each edge connecting two nodes u and v has a weight denoting the distance between them.

Your task is to find the shortest path distance from the source node (For this problem, it is the node labelled as 0) to all vertices given in the graph.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.

3. Print the maximum positive integer value, i.e 2147483647, for the disconnected nodes.

For Example:

alt text

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘u’, the second number denotes node ‘v’ and the third number denotes the distance between node ‘u’ and ‘v’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.
The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two single space-separated integers ‘V’ and ‘E’ denoting the number of vertices and the number of edges in the undirected graph, respectively.

The next ‘E’ lines each contain three single space-separated integers ‘u’, ‘v’, and ‘distance’, denoting a node ‘u’, a node ‘v’, and the distance between nodes (u, v) respectively.

Output format:

For each test case, print the shortest path distance from the source node, which is the node labelled as 0, to all vertices given in the graph in ascending order of the node number.  

Shortest path distance between source node and node labelled as 0 will be printed first followed by the distance between source node and node labelled as 1 and so on to the distance between source node and node labelled as ‘V-1’. 

Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the answer which is the shortest path distance from the source node (the node labelled as 0) to all vertices given in the graph in ascending order of the node number.

Constraints:

1 <= T <= 50
1 <= V <= 1000
1 <= E <= 3000
1 <= distance[u][v] <= 10^5

Where ‘T’ denotes the number of test cases, ‘V’ denotes the number of vertices in the graph, ‘E’ denotes the number of edges in the graph, and ‘distance[u][v]’ denotes the distance between node ‘u’ and ‘v’.

Time limit: 1 second

Accepted Answer

The question is about finding the shortest path distance from a source node to all vertices in an undirected graph.

The graph is represented by the number of vertices and edges, followed by the edges and their distances.
The task is to find the shortest path distance from the source node (0) to all other nodes.
If a node is disconnected from the source node, print the maximum positive integer value (2147483647).
Implement the function and return the shortest path distances in ascending order of the node number.

Accepted Answer

Using adjacency matrix

The idea is to maintain two arrays, one stores the visited nodes, and the other array stores the distance (element at index ‘i’ denotes the distance from node 0 to node ‘i’). We pick an unvisited minimum distance vertex, then update the distance of all its adjacent vertices considering the path from source to an adjacent vertex to pass through the picked minimum distance vertex. Repeat the process till all nodes are visited.

Steps:

We will make an adjacency matrix of size ‘V*V’, initialize all the positions to 0. Now, update the distance between two vertices in the matrix (denoted by the row number and column number) to the given distance in the input.
We also initialize the distance vector to ‘INT_MAX’ and the visited nodes vector to false. Since the distance of the source node i.e. node 0 to itself will be 0, update ‘distance[0]’ to 0.
Now, we find the shortest path for all vertices using the steps below:
1. We pick the minimum distance vertex, which is not yet visited, let’s say ‘u’. Mark it as true in the visited vector.
2. We update the distances of the adjacent vertices. Update distance[v] only if vertex ‘v’ is not already visited and the current distance of the vertex ‘v’ is greater than the distance from source vertex 0 to vertex ‘u’ plus the distance from ‘u’ to ‘v’.
3. Repeat the above steps till all the vertices are visited.
Return the distance vector, which is our required solution.

Space Complexity: O(1)Explanation:

O(V^2), where ‘V’ is the number of vertices in a graph.

The adjacency matrix takes the size of the order ‘V^2’.

Time Complexity: O(1)Explanation:

O(V^2), where ‘V’ is the number of vertices in a graph.

In the worst case, using a minimum distance node, distances of ‘V’ vertices are updated. So, using ‘V’ minimum distance nodes, vertices are updated ‘V^2’ times.

Python (3.5)

'''

    Time complexity: O(V^2)

    Space complexity: O(V^2)



    Where V is the number of vertices in the graph.



'''





# Finds the vertex with minimum distance

def minDistance(distance, visited, vertices):



    mini = 2147483647



    minVertex = 0



    for v in range(vertices):



        if (visited[v] == False and distance[v] <= mini):

            mini = distance[v]

            minVertex = v



    return minVertex





def dijkstraHelper(adjMat, vertices, source):



    distance = [2147483647 for i in range(vertices)]

    visited = [False for i in range(vertices)]



    # Distance of source to itself is 0.

    distance[source] = 0

    

    for i in range(vertices-1):

        u = minDistance(distance, visited, vertices)



        # Mark the current vertex as visied.

        visited[u] = True



        # Update the distances of the adjacent nodes.

        for v in range(vertices):

            if (not visited[v] and adjMat[u][v] and distance[u] != 2147483647 and distance[u] + adjMat[u][v] < distance[v]):

                distance[v] = distance[u] + adjMat[u][v]



    return distance





def dijkstra(edge, vertices, edges, source):



    adjMat = [[0 for i in range(vertices)] for j in range(vertices)]



    # Create an adjacency Matrix from the given input.F

    for i in range(edges):

        adjMat[edge[i][0]][edge[i][1]] = edge[i][2]

        adjMat[edge[i][1]][edge[i][0]] = edge[i][2]



    return dijkstraHelper(adjMat, vertices, source)

C++ (g++ 5.4)

/*

    Time complexity: O(V^2)

    Space complexity: O(V^2)



    where V is the number of vertices in the graph.

*/





// Finds the vertex with minimum distance

int minDistance(vector &distance, vector &visited, int vertices)

{

    int mini = INT_MAX, minVertex;



    for (int v = 0; v < vertices; v++) 

    {

        if (visited[v] == false && distance[v] <= mini) 

        {

            mini = distance[v];

            minVertex = v;

        }

    }



    return minVertex;

}





vector dijkstraHelper(vector> &adjMat, int vertices, int source)

{

    vector distance(vertices, INT_MAX);

    vector visited(vertices, false);



    // Distance of source to itself is 0.

    distance[source] = 0;



    for (int i = 0; i < vertices - 1; i++) 

    {

        int u = minDistance(distance, visited, vertices);

       

        // Mark the current vertex as visied.

        visited[u] = true;

        

        // Update the distances of the adjacent nodes.

        for (int v = 0; v < vertices; v++) 

        {

            if (!visited[v] && adjMat[u][v] && distance[u] != INT_MAX 

                    && distance[u] + adjMat[u][v] < distance[v]) 

            {

                distance[v] = distance[u] + adjMat[u][v];

            }

        }

    }

    

    return distance;

}





vector dijkstra(vector> &edge, int vertices, int edges, int source) 

{

    vector> adjMat(vertices, vector(vertices, 0));

    

    // Create an adjacency Matrix from the given input.

    for (int i = 0; i < edges; i++)

    {

        adjMat[edge[i][0]][edge[i][1]] = edge[i][2];

        adjMat[edge[i][1]][edge[i][0]] = edge[i][2];

    }



    return dijkstraHelper(adjMat, vertices, source);

}

Accepted Answer

Using the adjacency list

The idea is to use a priority queue which creates a min-heap for us. In the priority queue, we will be storing the ‘distance’ and node ‘v’ which will give us the minimum distance vertex. We will pick an unvisited minimum distance vertex which will be the first element of the priority queue, then update the distance of all its adjacent vertices (using adjacency list) considering the path from source to an adjacent vertex to pass through the picked minimum distance vertex. Repeat the process till the priority queue is empty.

Steps:

We will make an adjacency list that will be storing the two nodes between which an edge exists. We initialize the distance vector to ‘INT_MAX’ and the visited nodes vector to false.
Since the distance of the source node i.e node 0 to itself will be 0, update ‘distance[0]’ to 0.
Now, we find the shortest path for all vertices using the steps below:
1. Pick the first element of the priority queue, which will give the minimum distance vertex which is not yet visited, let’s say ‘u’. Pop it from the priority queue and mark it as true in the visited vector.
2. Iterate through the adjacency list to find all the adjacent vertices to the vertex ‘u’.
3. Now, update the distances of the adjacent vertices. Update distance[v] only if vertex ‘v’ is not already visited and the current distance of the vertex ‘v’ is greater than the distance from source vertex 0 to vertex ‘u’ plus the distance from ‘u’ to ‘v’.
4. Repeat the above steps till the priority queue is not empty.
Return the distance vector, which is our required solution.

Space Complexity: O(1)Explanation:

O(V^2), where ‘V’ is the number of vertices in a graph.

The adjacency list takes the size of the order ‘V^2’ in the worst-case scenario.

Time Complexity: O(1)Explanation:

O(E*log(V)), where ‘E’ is the number of edges and ‘V’ is the number of vertices in a graph.

The time taken to extract each vertex from the priority queue is (log(V)). So for V vertices, the time taken will be (V*log(V)). Insertion of a vertex in the priority queue takes log(V) time. So for total ‘E’ edges, the time taken will be E*log(V). So overall complexity will be O(V*log(V)) + O(E*log(V)) = O((E+V)*log(V)) ~ O(E*log(V)).

Python (3.5)

'''

    Time complexity: O(E*log(V))

    Space complexity: O(V^2)



    Where E is the number of edges 

    and V is the number of vertices in the graph.



'''





import heapq





def dijkstraHelper(adjList, vertices, source):



    pq = []



    distance = [2147483647 for i in range(vertices)]



    # Push the source vertex in the priority queue.

    pq.append([0, source])



    # Distance of a vertex to itself is 0.

    distance[source] = 0



    visited = [False for i in range(vertices)]



    # Loop till all vertices are visited.

    while (len(pq) > 0):



        pair = heapq.heappop(pq)



        u = pair[1]



        visited[u] = True



        # Update the distances of the adjacent nodes.

        for it in adjList[u]:

            v = it[0]

            dist = it[1]



            if (visited[v] == False and distance[v] > distance[u] + dist):

                distance[v] = distance[u] + dist

                heapq.heappush(pq, (distance[v], v))



    return distance





def dijkstra(edge, vertices, edges, source):



    adjList = [[] for j in range(vertices)]



    # Create an adjacency list.

    for i in range(len(edge)):

        adjList[edge[i][0]].append([edge[i][1], edge[i][2]])

        adjList[edge[i][1]].append([edge[i][0], edge[i][2]])



    return dijkstraHelper(adjList, vertices, source)

C++ (g++ 5.4)

/*

    Time complexity: O(E*log(V))

    Space complexity: O(V^2)



    where E is the number of edges and V is the number of vertices in the graph.

*/





#include 





vector dijkstraHelper(vector>> &adjList, int vertices, int source) 

{

    priority_queue, vector>, greater>> pq;

    

    vector distance(vertices, INT_MAX);

    

    // Push the source vertex in the priority queue.

    pq.push({0, source});

    

    // Distance of a vertex to itself is 0.

    distance[source] = 0;

    

    vector visited(vertices, false);

    

    // Loop till all vertices are visited.

    while (!pq.empty()) 

    {

        int u = pq.top().second;

        

        pq.pop();

        

        visited[u] = true;

        

        // Update the distances of the adjacent nodes.

        for (auto it = adjList[u].begin(); it != adjList[u].end(); it++) 

        {

            int v = (*it).first;

            int dist = (*it).second;



            if (visited[v] == false && distance[v] > distance[u] + dist) 

            {

                distance[v] = distance[u] + dist;

                

                pq.push({distance[v], v});

            }

        }

    }



    return distance;

}





vector dijkstra(vector> &edge, int vertices, int edges, int source) 

{

    vector>> adjList(vertices);

    

    // Create an adjacency list.

    for (int i = 0; i < edge.size(); i++) 

    {

        adjList[edge[i][0]].push_back({edge[i][1], edge[i][2]});

        adjList[edge[i][1]].push_back({edge[i][0], edge[i][2]});

    }



    return dijkstraHelper(adjList, vertices, source);

}

You have been given an undirected graph of ‘V’ vertices (labelled from 0 to V-1) and ‘E’ edges. Each edge connecting two nodes u and v has a weight denoting the distance between them.

Your task is to find the shortest path distance from the source node (For this problem, it is the node labelled as 0) to all vertices given in the graph.

Note:

For Example:

Input format:

Output format:

Constraints:

Top JUSPAY Front end Developer interview questions & answers

Popular interview questions of Front end Developer