Dijkstra's shortest path
You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

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 ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’. 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.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph. 2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

Input format:

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two integers ‘V’ and ‘E', denoting the number of vertices in the undirected graph and the number of edges in the undirected graph respectively. The next ‘E’ lines contain three space-separated integers ‘X’, ‘Y’, and ‘DISTANCE’, denoting a node ‘X’, a node ‘Y’, and the distance between nodes ‘X’ and ‘Y’ respectively.

Output format:

For each test case, print a single line containing ‘V’ space-separated integers that denote the shortest distance for each node from 0 to ‘V’-1, considering that we need the shortest distance from source node 0. Print the maximum positive integer value, i.e 2147483647, for the disconnected graph. Output for each test case will be printed in a separate line.

Note

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Dijkstra's shortest path

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

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 ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

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.

Note:

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

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

Input format:

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

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

The next ‘E’ lines contain three space-separated integers ‘X’, ‘Y’, and ‘DISTANCE’, denoting a node ‘X’, a node ‘Y’, and the distance between nodes ‘X’ and ‘Y’ respectively.

Output format:

For each test case, print a single line containing ‘V’ space-separated integers that denote the shortest distance for each node from 0 to ‘V’-1, considering that we need the shortest distance from source node 0.

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

Output for each test case will be printed in a separate line.

Note

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 50
1 <= V <= 1000
1 <= E <= 3000
0 <= X, Y < V
1 <= DISTANCE[X][Y] <= 10^5


Time limit: 1 sec

Accepted Answer

Dijkstra's Algorithm basically starts at the source node and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
Once the shortest path between the source node and another node is found, that node is marked as "visited" and added to the path.
The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.
To implement Dijkstra, priority queue can be used.

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.

The Steps are as follows:

We are given three variables, two nodes, and the distance between them. We need to form an adjacency matrix from this given information. For this, take a 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.
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.
Find the shortest path for all vertices using the steps below:
- Pick the minimum distance vertex, which is not yet visited, let’s say ‘X’.
- Mark it as true in the visited vector.
- Update the distances of the adjacent vertices. Update distance[Y] only if vertex ‘Y’ is not already visited and the current distance of the vertex ‘Y’ is greater than the distance from source vertex 0 to vertex ‘X’ plus the distance from ‘X’ to ‘Y’. This means that the shortest path from the source vertex to vertex ‘Y’ passes through vertex ‘X’.
- Repeat the above steps till all the vertices are visited.

5. Return the ‘DISTANCE’ vector, which is our required solution.

Space Complexity: O(n^2)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’. Hence the overall space complexity will be O(V^2).

Time Complexity: O(n^2)Explanation:

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

In the worst case, using a minimum distance vertex, distances of ‘V’ vertices are updated. So, using ‘V’ minimum distance vertices, vertices are updated ‘V^2’ times. Hence the overall complexity is O(V^2).

Java (SE 1.8)

/*

    Time complexity: O(V^2)

    Space complexity: O(V^2)



    Where 'V' is the number of vertices in a graph.

*/



import java.util.*;



public class Solution {



    // Finds the vertex with minimum distance.

    public static int minDistance(ArrayList < Integer > distance, ArrayList < Boolean > visited, int vertices) {

        int min = Integer.MAX_VALUE;

        int minVertex = 0;



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

            if (visited.get(v) == false && distance.get(v) <= min) {

              min = distance.get(v);

              minVertex = v;

            }

        }

        return minVertex;

    }



    public static ArrayList < Integer > dijkstraHelper(int[][] matrix, int vertices, int source) {

        

        ArrayList < Integer > distance = new ArrayList < Integer > (vertices);

        ArrayList < Boolean > visited = new ArrayList < Boolean > (vertices);

        

        for (int i = 0; i < vertices; i++) {

            distance.add(Integer.MAX_VALUE);

            visited.add(false);

        }



        // Distance of source to itself is 0.

        distance.set(source, 0);



        for (int i = 0; i < vertices; i++) {

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



            // Mark the current vertex as visied.

            visited.set(u, true);



            // Update the distances of the adjacent nodes.

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

                if (!visited.get(v) && matrix[u][v] != 0 && distance.get(u) != Integer.MAX_VALUE && distance.get(u) + matrix[u][v] < distance.get(v)) {

                    distance.set(v, distance.get(u) + matrix[u][v]);

                }

            }

        }



        return distance;

    }



    public static ArrayList < Integer > dijkstra(ArrayList < ArrayList < Integer > > vec, int vertices, int edges, int source) {

  	

        int[][] matrix = new int[vertices][vertices];

        

        // Create an adjacency matrix from the given input.

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

            int u = vec.get(i).get(0);

            int v = vec.get(i).get(1);

            int w = vec.get(i).get(2);

            if (matrix[u][v] != 0) {

                matrix[u][v] = Math.min(matrix[u][v], w);

                matrix[v][u] = Math.min(matrix[v][u], w);

            } else {

                matrix[u][v] = w;

                matrix[v][u] = w;

            }

        }



        return dijkstraHelper(matrix, vertices, source);

    }

}

Python (3.5)

'''

    Time complexity: O(V^2)

    Space complexity: O(V^2)



    Where 'V' is the number of vertices in a graph.

'''



import sys



# Finds the vertex with minimum distance.

def minDistance(distance, visited, vertices):

    min = 2147483647

    minVertex = 0

    for v in range(vertices):

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

            min = distance[v]

            minVertex = v



    return minVertex





def dijkstraHelper(matrix, vertices, source):

    distance = [2147483647] * vertices

    visited = [False] * vertices



    # Distance of source to itself is 0.

    distance[source] = 0



    for i in range(vertices):

        u = minDistance(distance, visited, vertices)

        # Mark the current vertex as visited.

        visited[u] = True

        # Update the distances of the adjacent nodes.

        for v in range(vertices):

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

                distance[v] = distance[u] + matrix[u][v]



    return distance





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

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

    

    # Create an adjacency matrix from the given input.

    for i in range(len(vec)):

        u = vec[i][0]

        v = vec[i][1]

        w = vec[i][2]

        if(matrix[u][v]!=0):

            matrix[u][v]=min(matrix[u][v],w)

            matrix[v][u]=min(matrix[v][u],w)

        else:

            matrix[u][v]=w

            matrix[v][u]=w



    return dijkstraHelper(matrix, vertices, source)

C++ (g++ 5.4)

/*
    Time complexity: O(V^2)
    Space complexity: O(V^2)

    Where â€˜Vâ€™ is the number of vertices in a graph.
*/

// Finds the vertex with minimum distance.
int minDistance(vector distance, vector visited, int vertices) {
    int min = INT_MAX, minVertex;
    
    for (int v = 0; v < vertices; v++) {
        if (visited[v] == false && distance[v] <= min) {
            min = distance[v];
            minVertex = v;
        }
    }
    return minVertex;
}

vector dijkstraHelper(vector> &matrix, 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; 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] && matrix[u][v] && distance[u] != INT_MAX && distance[u] + matrix[u][v] < distance[v]) {
                distance[v] = distance[u] + matrix[u][v];
            }
        }
    }
    return distance;
}

vector dijkstra(vector> &vec, int vertices, int edges, int source) {
    vector< vector> matrix(vertices, vector(vertices,0));

    // Create an adjacency matrix from the given input.F
    for (int i = 0; i < vec.size(); i++) {
        int u = vec[i][0];
        int v = vec[i][1];
        int w = vec[i][2];
        if(matrix[u][v]!=0){
            matrix[u][v]=min(matrix[u][v],w);
            matrix[v][u]=min(matrix[v][u],w);
        }
        else{
            matrix[u][v]=w;
            matrix[v][u]=w;
        }
    }
    return dijkstraHelper(matrix, vertices, source);
}

Accepted Answer

Using The Adjacency List.

The idea is to use a priority queue which creates a min-heap for us. The priority queue sets a priority for every element added to it based on the size of the added element. In the priority queue, we will be storing the ‘DISTANCE’ and node ‘Y’ which will give us the minimum distance vertex.

In our case, priority will be set based on the distance. 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.

The Steps are as follows:

We are given three variables, 2 nodes, and the distance between them. We need to form an adjacency list from this given information. For this, make an adjacency list that will be storing the two nodes between which an edge exists.
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.
Find the shortest path for all vertices using the steps below:
- Pick the first element of the priority queue, which will give the minimum distance vertex which is not yet visited, let’s say ‘X’. Pop it from the priority queue.
- Mark it as true in the visited vector.
- Iterate through the adjacency list to find all the adjacent vertices to the vertex ‘X’.
- Now, update the distances of the adjacent vertices. Update ‘DISTACNE[Y]’ only if vertex ‘Y’ is not already visited and the current distance of the vertex ‘v’ is greater than the distance from source vertex 0 to vertex ‘X’ plus the distance from ‘X’ to ‘Y’. This means that the shortest path from the source vertex to vertex ‘X’ passes through vertex ‘Y’. Push the adjacent vertices along with their distances to the priority queue.
- Repeat above steps until the priority queue is empty.

5. Return the ‘DISTANCE’ vector, which is our required solution.

Space Complexity: O(n)Explanation:

O(E), where ‘E’ is the number of edges in a graph.

The adjacency list takes the size of the order ‘E'. Hence the overall space complexity will be O(E).

Time Complexity: OtherExplanation:

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 O(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 O(E * log(V))

So overall complexity will be O(V * log(V)) + O(E * (V)) = O( (E + V) * log(V) ) = O(E * log(V))