Shortest path from one source which goes through N edges ?

Question

0.00/5 (No votes)

See more:

In my economics research I am currently dealing with a specific shortest path problem:

Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from one source S, which goes through N edges. The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.

Is there an efficient algorithm for this problem?

What I have tried:

For now I can only compute shortest path when I know the final vertex as a constraint, but now I want my constraint to be on the number of edges the paths go through and not on the final vertex.

Posted 28-Jun-18 23:39pm

Alexandre Cornet

Updated 29-Jun-18 6:33am

Add a Solution

Comments

[no name] 29-Jun-18 20:01pm

So you're saying I can "reverse" in order to "shorten" my path by picking a negative edge that returns to a previous vertex that has any number of edges?

The potential then exists to cycle into a negative black hole?

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2018-06-29T06:34:00

Solution 1

Quote:
Is there an efficient algorithm for this problem?

None, even worse there can be no solution because of infinite looping.

Quote:
The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.

The combination of those criteria can lead to infinite loops.
If you have a loop with negative cost, just 1 more loop will improve any best path infinitely.
Negatives costs prevent any optimization.

You have to rethink your criteria or give details.

Posted 29-Jun-18 6:34am

Patrice T

Comments

Alexandre Cornet 29-Jun-18 15:56pm

You have to explain me how there can be an infinite loop with only N edges ;)
Maybe I forgot to precise that N is a finite natural number...
thanks anyway.

Patrice T 29-Jun-18 16:09pm

You stated : 'the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.'
This imply possible infinite loop.

Alexandre Cornet 29-Jun-18 16:13pm

Such loops may exists but I am only looking at path with a finite number of edges. Therefore I would have guessed that because of this finite number of edge constraint this kind of loop would not be a problem.

Patrice T 29-Jun-18 16:28pm

Path with limited number of steps is same as shortest path!

Alexandre Cornet 29-Jun-18 16:42pm

by shortest path I meant : the path with the least weight not the least edges.

Patrice T 29-Jun-18 16:48pm

Shortest path means: path with least cost between poit A and point B.
Shortest path problem - Wikipedia[^]

Alexandre Cornet 29-Jun-18 17:01pm

Yes this is what I am saying...
"In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized"

Patrice T 29-Jun-18 17:12pm

May be you should update the question with an explanation of what is your 'shortest path'

Alexandre Cornet 29-Jun-18 17:18pm

Ok thanks anyway