CODEWITHSUNDEEP
algorithmgraph
user3634974
user3634974

Reputation: 111

Longest Path, with Ascending Edges Weights, in Cyclic Undirected Graph

I want to find longest path in cyclic undirected graph. Each pair of edge is associated with a cost.

The constraint on traversing is that the weight should be in ascending order. Thus I want to find longest path with ascending weights.

Can we use DFS to solve the problem. I am trying to implement it but I don't know how to take care of cycles.

Upvotes: 2

Views: 1407

Answers (3)

Marcin Panasiuk
Marcin Panasiuk

Reputation: 21

You could create a directed graph G' where vertices represent edges in the original one. In graph G' there is path from vertex A' to vertex B' if corresponding edges A->B create an ascending path. Now the problem can be stated as finding longest path in the graph G'. The graph G' is a DAG and we can sort it topologically and find the longest path in simple traverse.

Upvotes: 2

Khaled.K
Khaled.K

Reputation: 5940

Here's my approach ..

Branch

stack = create empty stack
branched = create empty list
tree = create empty tree

stack.push({node=start_node, distanct=0, tree.root})
tree.root = start_node
branched.add(start_node)

while stack is not empty:
{
    current_node = stack.pop()

    if current_node is end_node:
        skip

    for each neighbour_node of current_node:
    {

        if neighbour_node is parent of current_node.getTreeNode():
            skip

        if neighbour_node exist in branched list:
            current_node.getTreeNode().addChild(neighbour_node, TYPE_LINK)
        else:
            current_node.getTreeNode().addChild(neighbour_node, TYPE_BRANCH)
            stack.push(neighbour_node)
    }
}

This branching is optimal, since whenever a visited node is branched, we will insert it in the tree as a LINK, which we will be using later on to maximize or minimize in order to find unique paths that contain no cycles between start_node and end_node.

Optimization

tree2 = create empty tree
tree2.root = empty_node

for each leaf in tree.getLeaves():
    if leaf is end_node:
        tree2.root.addPath(tree.getPath(leaf).reverse())

for each leaf in tree.getLeaves():
    if leaf is TYPE_LINK:
        L = tree2.findAll(leaf)    
        for each node in L:
            if L.getChildren() doesn't contain this node:
                L.addPath(tree.getPath(node).reverse())

solution = { none, 0 }

for each leaf in tree2.getLeaves():
    if leaf is start_node AND leaf.depth > solution.depth:
        solution = leaf

return solution

First we take end_node and form a tree2, first find direct paths toward start_node, then add liked paths as branches. Finally, we take the deepest leaf.

Upvotes: 1

user3386109
user3386109

Reputation: 34829

If the only constraint of traversing is that the weight continuously increases, then you don't need to worry about cycles. Eventually each cycle will terminate due to the fact that you entered a vertex on the highest weighted edge, and therefore there is no edge that is valid for exiting the vertex.

Upvotes: 4

Related Questions