Problem: Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph. Please find the reference graph: lin...

I am trying to find out if it is possible to use Dijkstra's algorithm to find the longest path in a directed acyclic path. I know that it is not possible to find the longest path with Dijkstra in a...

In this tree: a / \ b d / / \ c e f / g The longest path starting from the root would be a-d-f-g Here is my attempt: class Node: def __init__(self, x): self.val = x self.left = None ...

I'm having trouble figuring out how to update the networkx dag_find_longest_path() algorithm to return "N" for ties instead of returning the first max edge found, or returning a list of all edges t...

I am trying to solve a program, where in I have to find the max number of cities connected for a given list of routes. for eg: if the given route is [['1', '2'], ['2', '4'], ['1', '11'], ['4', '1...

I know that for non-directed graph this problem is NP-complete hence we should do Brute Force in order to check all possible paths. How we can do that? Please suggest a pseudo code and tell me the ...

I have a list of nations, and I want to have the longest path of nations where each country chosen must begin with the same letter that ended the previous element nations = ['albania','andorra','a...

What optimizations exist for trying to find the longest path in a cyclic graph? Longest path in cyclic graphs is known to be NP-complete. What optimizations or heuristics can make finding the longe...

I need to program a Lisp function that finds the longest path between two nodes, without revisiting any nodes. Though, if the start and end node are the same, this node can be revisited. The functi...

I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine...