Shortest path in Undirected Graph | GFG POTD 21st Aug 2024 | JAVA | C++

#gfgpotd #gfgpotdtoday #potd #gfgproblemoftheday #problemoftheday

[@ajinkyajain2302]

C++ Code : vector shortestPath(vector& edges, int N,int M, int src){ // code here vector adj(N); for (const auto& edge : edges) { adj[edge[0]].push_back(edge[1]); adj[edge[1]].push_back(edge[0]); } // Distance array vector dis(N, INT_MAX); dis[src] = 0; // BFS queue q; q.push(src); while (!q.empty()) { int cur = q.front(); q.pop(); for (int nbr : adj[cur]) { if (dis[cur] + 1 < dis[nbr]) { dis[nbr] = dis[cur] + 1; q.push(nbr); } } } // Replace unreachable nodes' distance with -1 for (int i = 0; i < N; ++i) { if (dis[i] == INT_MAX) { dis[i] = -1; } } return dis; }

[@ajinkyajain2302]

JAVA Code : public int[] shortestPath(int[][] edges,int n,int m ,int src) { // Code here ArrayList adj = new ArrayList(); for(int i = 0 ; i < n ; ++i){ adj.add(new ArrayList()); } for(int[] edge : edges){ adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } int[] dis = new int[n]; Arrays.fill(dis, Integer.MAX_VALUE); dis[src] = 0; Queue q = new LinkedList(); q.add(src); while(!q.isEmpty()){ int cur = q.poll(); for(int nbr : adj.get(cur)){ if(dis[cur] + 1 < dis[nbr]){ dis[nbr] = dis[cur] + 1; q.add(nbr); } } } for(int i = 0; i < n; ++i){ if(dis[i] == Integer.MAX_VALUE){ dis[i] = -1; } } return dis; }

[@creativesruffs5008]

subscribed