Finding longest path of a specially-shaped graph in O(Log(n))

First of all let’s clear thing up:

Finding the longest path of a graph algorithm is NOT the inverse of Dijkstra’s algorithm of finding the shortest path. In fact finding the longest path of a graph in NP-Hard problem.

In our case, the graph is a tree-shaped graph, more like a triangle.

Our goal here is to find the longest path from top to bottom.

Example:
Note how we select each node leading us to the longest path:

STOP and think about an algorithm to solve this problem.
I will be posting the algorithm along with an implementation in C++ sometimes soon.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

This site uses Akismet to reduce spam. Learn how your comment data is processed.