Implementing Dijkstra Algorithm

Problem Statement - link #

Given a weighted, undirected and connected graph of V vertices and E edges, Find the shortest distance of all the vertex’s from the source vertex S. Note: The Graph doesn’t contain any negative weight cycle.

Your Task: You don’t need to read input or print anything. Your task is to complete the function dijkstra() which takes the number of vertices V and an adjacency list adj as input parameters and returns a list of integers, where ith integer denotes the shortest distance of the ith node from the Source node. Here adj[i] contains a list of lists containing two integers where the first integer j denotes that there is an edge between i and j and the second integer w denotes that the weight between edge i and j is w.

Expected Time Complexity: O(V^2)
Expected Auxiliary Space: O(V^2)

Examples #

Example 1:

Input:
V = 3, E = 3
u = 0, v = 1, w = 1
u = 1, v = 2, w = 3
u = 0, v = 2, w = 6
adj = [[[1, 1], [2, 6]], [[2, 3], [0, 1]], [[1, 3], [0, 6]]]
S = 2
Output:
4 3 0
Explanation:

For nodes 2 to 0, we can follow the path-
2-1-0. This has a distance of 1+3 = 4,
whereas the path 2-0 has a distance of 6. So,
the Shortest path from 2 to 0 is 4.
The other distances are pretty straight-forward.

Constraints #

• 1 ≤ V ≤ 1000
• 0 ≤ adj[i][j] ≤ 1000
• 1 ≤ adj.size() ≤ [ (V*(V - 1)) / 2 ]
• 0 ≤ S < V

Solutions #

class Solution
{
    public:
	//Function to find the shortest distance of all the vertices
    //from the source vertex S.
    vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    {
        // Code here
        vector<int> vis(V,0);
        vector<int> dis(V,INT_MAX);
        dis[S]=0;
        for(int count=0;count<V-1;count++){
            int u = -1;
            for(int i=0;i<V;i++)
                if(!vis[i]&&(u==-1||dis[i]<dis[u])) u=i;
            vis[u]=1;
            for(int i=0;i<adj[u].size();i++){
                int j=adj[u][i][0];
                int w=adj[u][i][1];
                if(!vis[j]&&(dis[u]+w<dis[j]))
                    dis[j]=dis[u]+w;
            }
        }
        return dis;
    }
};