fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int main(){
  10.  
  11.   //  freopen("t.txt", "r", stdin);
  12.  
  13.     int nodes, edges;
  14.     cin >> nodes >> edges;
  15.  
  16.     vector<vector<int>> graph(nodes + 1);
  17.  
  18.     vector<int> distance(nodes + 1, -1);
  19.     vector<int> parent(nodes + 1);
  20.     vector<int> shortestPath;
  21.  
  22.     queue<int> bfs;
  23.  
  24.     while(edges--){
  25.        int from, to;
  26.        cin >> from >> to;
  27.  
  28.        graph[from].push_back(to);
  29.        graph[to].push_back(from);
  30.     }
  31.  
  32.     int src = 1;
  33.     bfs.push(src);
  34.     distance[src] = 0;
  35.     parent[src] = src;
  36.  
  37.  
  38.     while(!bfs.empty()){
  39.         int node = bfs.front();
  40.         bfs.pop();
  41.  
  42.         for(int child : graph[node]){
  43.             if(distance[child] == -1){
  44.                 bfs.push(child);
  45.  
  46.                 distance[child] = distance[node]+1;
  47.                 parent[child] = node;
  48.             }
  49.         }
  50.  
  51.  
  52.     }
  53.     cout << '\n';
  54.     for(int node = 1; node <= nodes; node++)
  55.         cout << node <<" -> "<< distance[node] <<" Parent : "<< parent[node] <<'\n';
  56.  
  57.  
  58.     int dist = 7;
  59.  
  60.     cout <<"\nThe Shortest Path from "<< src <<" to "<< dist <<" is : ";
  61.  
  62.     shortestPath.push_back(dist);
  63.     do{
  64.         dist = parent[dist];
  65.         shortestPath.push_back(dist);
  66.     }while(dist != src);
  67.  
  68.     reverse(shortestPath.begin(), shortestPath.end());
  69.  
  70.     for(int node : shortestPath)
  71.         cout << node <<' ';
  72.  
  73.     cout <<"\nand The distance of Path is : "<< distance[shortestPath[shortestPath.size()-1]] <<'\n';
  74.  
  75.  
  76. }
  77.  
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
7 10
1 2
1 3
2 3
2 5
2 4
4 5
4 3
5 6
6 7
7 3
stdout
copy 
1 -> 0 Parent : 1
2 -> 1 Parent : 1
3 -> 1 Parent : 1
4 -> 2 Parent : 2
5 -> 2 Parent : 2
6 -> 3 Parent : 5
7 -> 2 Parent : 3

The Shortest Path from 1 to 7 is : 1 3 7 
and The distance of Path is : 2
https://ideone.com/j2w2Qm
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!