ronith
9/24/2018 - 9:46 AM

Longest path between any pair of vertices

``````// https://www.geeksforgeeks.org/maximum-edges-can-added-dag-remains-dag/
#include <bits/stdc++.h>
using namespace std;

class graph {
int v;
vector<int> indegree;
vector<int> *weight;
public:
graph(int v) {
this->v= v;
weight= new vector<int> [v];
for (int i=0;i<v; i++)
weight[i]= vector<int> (v, 0);
}
void addEdge(int u, int w, int x) {
weight[u][w]= x;
weight[w][u]= x;
}
void LP();
void DFSUtil (int , bool[], int&, int& , int );
};
void graph::DFSUtil(int s, bool visited[], int &currlen, int &maxlen, int parent) {
visited[s]=1;
bool flag= false;
list<int>::iterator i;
if (!visited[*i]) {
flag= true;
currlen+= weight[s][*i];
DFSUtil(*i, visited, currlen, maxlen, s);
}
}
if (!flag) {
cout<<s<< "-"<< currlen << " ";
if (currlen>maxlen)
maxlen= currlen;
}
if (parent!= -1)
currlen-= weight[parent][s];
}
void graph::LP() {
int maxlen= INT_MIN;
for (int i=0; i<v; i++) {
cout<< i<< ":\n";
bool visited[v]= {0};
int currlen=0;
DFSUtil (i, visited, currlen, maxlen, -1);
cout<< "\n";
}
cout<< "Longest path is: "<< maxlen;
}

int main() {
graph g(6);