Count the longest path in a directed graph

Question

1.00/5 (1 vote)

See more:

, +

I have this question for ADS passionates. There is a procedure graph. Let's imagine like this. Below I described a graph using an adj list.

adjList = {

A: [B, D],
B: [C],
C: [],
D: [E]
E: [F]
F: []
}

How can you find and count the longest path?
Edge cases:
1. If you find a cycle in the graph return "cycle found", otherwise return the count of the longest path.
2. There may be a case some of the nodes may not be connected. i.e A->B->C D->E. Here D->E nodes are separate from the rest of the nodes.

What I have tried:

I tried to solve the problem. But in my case, I couldn't return the count but I put them into an array. Still, it is not solving the problem, I ended up collecting all the paths into an array.

I used DFS. But I heard that if I use DFS and DP with graph I can solve the problem. Can help me out with this problem?

Javascript, C++, and Java even Python codes are welcome!

Posted 10-Jan-22 13:11pm

sharopcha

Updated 18-Jan-22 7:05am

Add a Solution

Comments

Stefan_Lang 11-Jan-22 5:23am

Do not assume that anyone reading your question is familiar with the specific methods you happened to have come across, or familiar with the specific names of these methods that you know, even if they do know the method as such. Methods and algorithms tend to be known by different names depending on your source. And not every source introduces abbreviations for such names at all. Therefore abbreviations such as DFS or DP are not helpful!

At the very least provide names that are concise enough to be googled, so the reader will be able to look up if it happens to be something he is familiar with under a different name.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2022-01-10T21:53:00

Solution 1

Quote:
Javascript, C++, and Java even Python codes are welcome!

Sorry, this site does not provide code to order. This is your assignment so you are expected to do the work. People here will help with your code if you have specific problems, but no one is going to do your work for you.

Posted 10-Jan-22 21:53pm

Richard MacCutchan

Comments

sharopcha 11-Jan-22 4:55am

Actually, I don't want a code. I have a code written already. If you've paid attention to my request I've asked how to improve it with DP. Need help with some logic.

Stefan_Lang 11-Jan-22 5:17am

1. Given how many abbreviations exist in various contexts, you would do well to actually use full names. I have no idea what you are talking about.
2. This may not be the right place to ask, unless you have a concrete issue where you don't know how to implement something with C++ or another programming language - QA is not meant to provide you with the 'something' part, because that would not qualify for the 'Q' (quick) in 'QA'

Richard MacCutchan 11-Jan-22 6:21am

As I mentioned above, this site is for specific problems. We have no idea what your code is doing, or supposed to do, or what problems need correcting. Without that information there is very little that anyone can suggest.

Greg Utas · Answer 2 · 2022-01-16T04:54:00

It is very unlikely that anyone will write this code for you.

I assume that DFS = depth-first search. That will work, but you have to do a DFS starting from each node in the graph. During the search, you'll need to pass a vector of the nodes reached so far, so that you can check if the next node to be added to a path has already been reached (which indicates a cycle).

I don't know what you mean by DP, however.

Member 15502389 · Answer 3 · 2022-01-18T07:05:00

Hello,
That's my solution:

1) Use Tarjan's strongly connected components algorithm to find all connected components,

2) If there is any component larger then 1, you have cycle, so your algorithm should return cycle found,

3) If there isn't, you end up with DAG (Directed Acyclic Graph), so you can find topological order (note: if you correctly implement Tarjan's algorithm you also found needed order), for example using DFS algorithm

4) Then go through your DAG after toposorting, and make use of some Dynamic Programming on DAG (this is which DP stands for). So in each vertex store length of the longest path ending in this vertex. To calculate that length use simple formula iterating through each u: len[v] = max(len[v], len[u] + 1) where u is v's father.

5) Then the greatest len[i] (for any i) is your result!

And this is my c++ code for your problem:

C++

const int N = 1e9; // MAX vertices count
vector<int> digraph[N], transpose[N], postorder; // adjacency lists DS
bool visited[N]; // array for counting visited nodes
int n, m, len[N]; // number of vertices and edges

void DFS(int v) {
    visited[v] = true;
    for (int u : digraph[v])
        if (visited[u] == false)
            DFS(u);
    
    postorder.push_back(v);
}

void DFS_2(int v) {
    visited[v] = true;
    for (int u : transpose[v])
        if (visited[u] == false)
            DFS_2(u);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        digraph[u].push_back(v);
        transpose[v].push_back(u);
    }

    for (int v = 1; v <= n; v++)
        if (visited[v] == false)
            DFS(v); // calculating post order, first step of Tarjan's alg
    
    reverse(postorder.begin(), postorder.end());

    for (int v = 1; v <= n; v++)
        visited[v] = false;

    int c = 0; // c is number of strongly connected components
    for (int v : postorder)
        if (visited[v] == false)
            c++, DFS_2(v);

    if (c < n) cout << "cycle found";
    
    int longest = 0; // variable for result 
    for (int v : postorder)
        for (int u : transpose[v])
            len[v] = max(len[v], len[u] + 1);
        longest = max(longest, len[v]);

    cout << "the longest path in graph: " << longest;
}

In terms of time complexity we've got O(n+m) (n is number of nodes and m is number of edges).

Count the longest path in a directed graph

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0