CODEWITHSUNDEEP
algorithmgraphgraph-theorygraph-algorithm
MrMartin
MrMartin

Reputation: 467

Shortest path in directed graph with cycles of negative length

Is there an algorithm for finding the shortest path in a directed graph which includes cycles of negative length? The constraint is that each node can only be visited once, so the solution exists.

I'm aware of the Bellman-Ford algorithm, but it fails when negative cycles are present. It's also clear that traversing negative cycles forever makes the problem ill-defined, so I'm constraining the path to visit each node at most once.

Is there such an algorithm? And is there an off-the-shelf implementation I can use?

---EDIT---

As requested below, here's the actual application:

Given an input image containing handwriting, I can estimate probabilities of stroke directions at each pixel: enter image description here

Then, I can put the pixels into a graph, and find the path of the pen: enter image description here

See how the "l" is missed out? If I can set the adjacent weights to be negative, the optimal path will traverse all letters. But negative weights create negative cycles.

Upvotes: 0

Views: 917

Answers (1)

Zargles
Zargles

Reputation: 347

You are right that the Bellman-Ford algorithm fails in this case. You can refer section 2 of this resource. It discusses the problem for an undirected graph and works based on Edmonds' Minimum Weight Perfect Matching Algorithm. In fact, you might be interested in this question, which is very similar to yours.

When the graph is a directed one, then as @SaiBot pointed out, the problem reduces to an NP Hard problem, and there is no efficient solution possible.

Upvotes: 1

Related Questions