-4

I was asked this question on an interview coding assignment. While i was unsuccessful to complete this task, I was wondering if anyone can help me understand how this can be done.

Question: You are given number of nodes and edges. With that you are given two arrays: g_From[] and g_To[]. you are to find the maximum distance between two nodes.

Input:

First line consists of two integers, Number of nodes n and edges e.

Next e lines consists of g_From and g_To

example:

5 6 //Number of Nodes = 5, edges = 6. Following 6 line are to-from

1 2 //g_from[0] = 1, g_to[0] = 2 => from node 1 to node 2

1 3 //g_from[1] = 1, g_to[1] = 3 => from node 1 to node 3

2 3 //g_from[2] = 2, g_to[2] = 3 => from node 2 to node 3

2 4 //g_from[3] = 2, g_to[3] = 4 => from node 2 to node 4

3 4 //g_from[4] = 3, g_to[4] = 4 => from node 3 to node 4

4 5 //g_from[5] = 4, g_to[5] = 5 => from node 4 to node 5 

Output:
4

Explanation:
As you can see from the inputs there are many ways to traverse
for example: 

1->3->4->5

2->3->4->5

but the longest route is: 1->2->3->4->5

The distance is 5-1 = 4, answer!

Luai Ghunim
  • 976
  • 7
  • 14
Yash Shah
  • 13
  • 4
  • 1
    And what is your question? Are you expecting someone here to write the code for you? That is certainly not going to happen, as this site is not a homework help or code-writing site. Please post the code you have, along with an explanation of what specific problem you are having. Also visit the [help] and read [ask] to learn how to use this site. – Jim Garrison Nov 22 '17 at 01:17
  • 1
    http://idownvotedbecau.se/noresearch/ Straightforward graph algorithms are treated quite thoroughly on Stack Overflow, Wikipedia, and elsewhere. – Prune Nov 22 '17 at 01:41

2 Answers2

0

create two int arrays namely g_from and g_to
create function traverse to traverse through the array by calling function traverse and place toNode as parameter and each time add 1 to length
create function findLongestRoute to find the longest route

private int[] g_from = new int[6];
private int[] g_to = new int[6];

public Integer traverse(Integer fromNode,Integer length) {
    for(int i = 0; i < g_from.length; i++) {
        if(g_from[i] == fromNode) {
            return traverse(g_to[i],++length);
        }
    }
    return length;
}

public Integer findLongestRoute() {
    int l = 0;

    for(int i = 0; i < g_from.length; i++) {
        int length = traverse(g_from[i],0);
        if(length > l) {
            l = length;
        }
    }

    return l;
}
Frank Ngai
  • 16
  • 2
0

Since the cost is positive, so Dijsktra will work.

Invert the values from positive to negative and then run shortest-path Algorithm.

The founded path will be the longest , at the end take abosolute value of the cost.

Luai Ghunim
  • 976
  • 7
  • 14
  • it won't work as https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag stated here – noman pouigt Nov 23 '17 at 00:04
  • @nomanpouigt that guy has negative weights and Dijkstra does not work with engative weights , here we don't have negative weights. – Luai Ghunim Nov 23 '17 at 00:09
  • oh but changing positive to negative doesn't change it to negative weights? – noman pouigt Nov 23 '17 at 00:44
  • Also https://www.quora.com/Can-we-modify-Dijkstra-to-compute-longest-path-for-DAG-graph – noman pouigt Nov 23 '17 at 00:48
  • Then all weights are negative and Dijkstra does not work if few weights are positive and other are negative but it works if al weights are negative, because you can get a cycle and Dijkstra does not handle cycles. – Luai Ghunim Nov 23 '17 at 00:53
  • then according to you "longest path with all positive weights in a DAG same as shortest path finding usind djikstra with weight sign inverted"? – noman pouigt Nov 23 '17 at 02:00
  • @nomanpouigt run it one time and see what happends, it will explore all node but it will find a path with shortest (negative) weight and if since -5 < -4 then absolute value will be 5 which will be largest path – Luai Ghunim Nov 23 '17 at 04:19