1
$\begingroup$

Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.

I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.

I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.

Thanks


EDIT:

My problem is similar to a-Autonomy Shortest Paths: I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.

So for example given this graph:

S--R1--R2--F--D
\······················/
··Z1----------Z2

Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.
This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.
As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.

I don't know whether I made it to clarify my self or not....but it would be nice if you give me any hint on how to do it.

Thanks

$\endgroup$
5
  • $\begingroup$ If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices). $\endgroup$
    – Eff
    Aug 6, 2014 at 20:56
  • $\begingroup$ It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work. $\endgroup$
    – qaphla
    Aug 6, 2014 at 21:05
  • $\begingroup$ Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks $\endgroup$
    – cama
    Aug 6, 2014 at 21:55
  • $\begingroup$ Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $\le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $\le k$ for $k$ from $1$ to $n$. $\endgroup$
    – xavierm02
    Aug 6, 2014 at 22:06
  • $\begingroup$ This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value). $\endgroup$
    – xavierm02
    Aug 6, 2014 at 22:06

2 Answers 2

1
$\begingroup$

Instead of modifying Dijkstra’s algorithm, you can modify the input graph. Create a “layered” graph with nodes $(i,k)$, where $i$ is an original node and $k$ is the number of hops so far, and edges from $(i,k)$ to $(j,k+1)$, where $(i,j)$ is an original edge.

$\endgroup$
0
$\begingroup$

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.

Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:

  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there
  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)

In this way, you should be able to remove the paths that are going to violate the constraint.

$\endgroup$
1
  • $\begingroup$ Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $\pi_1$ and $\pi_2$ from source to some vertex $v$ such that $\pi_1$ uses one edge, while $\pi_2$ uses two. If $\pi_2$ is shorter than $\pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem. $\endgroup$ Mar 2, 2017 at 1:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .