3
$\begingroup$

I was wondering to know whether Dijkstra's algorithm can find the optimal solution for a weighted and directed shortest paths problem where: 1) for each arc $(i,j)$, $i>j$ and 2) it is not always possible to go from vertex $i$ to vertex $j$ if $i>j$ (some other constraints should be satisfied too). Note that vising all vertices is not mandatory; we just need to go from vertex $0$ to vertex $T$ (while respecting the problem constraints.)

Thanks.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you just mean that not all arcs exist? There are Dijkstra implementations for sparse graphs. If you really mean "constraints" (ie depending on something endogenous), then things could be more difficult. There are network algorithms that allow certain side constraints (typically linear). So in short, my cop-out would be: it depends. $\endgroup$
    – Erwin Kalvelagen
    Jun 13, 2021 at 8:45
  • $\begingroup$ Could you describe the problem more in detail ("some other constraints should be satisfied too")? Or give an example ? $\endgroup$
    – Kuifje
    Jun 13, 2021 at 13:35
  • $\begingroup$ @ErwinKalvelagen, due to the constraint, some of the arcs do not exist. The rest of the problem is similar to a weighted and directed shortest path problem. $\endgroup$
    – mdslt
    Jun 13, 2021 at 15:16
  • $\begingroup$ @Moosavi_69 The problem statement is a bit inconsistent. You say that for each arc $(i,j)$ $i > j$ (i.e., arcs go from higher numbered vertices to lower numbered vertices) and then that you need to go from vertex 0 (presumably the lowest numbered vertex) to vertex $T$ (presumably where $T > 0$). If arcs go from higher to lower vertices, you cannot get from 0 to $T$ (or anywhere else, for that matter). $\endgroup$
    – prubin ♦
    Jun 13, 2021 at 19:17

1 Answer 1

Reset to default
3
$\begingroup$

I'm assuming the goal here is shortest (least total weight) path. As long as the "problem constraints" affect the graph only to the extent of causing arcs to exist or not exist, and as long as the graph contains no negative cycles (closed paths whose aggregate weight is negative), Dijskstra's algorithm will work fine. If all arcs go from lower to higher index vertices (or all arcs go from higher to lower index vertices), the graph will be cycle free, which eliminates any chance of a negative cycle. Similarly, if the weights are all nonnegative, you do not have to worry about a negative weight cycle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ And if the graph is cycle free a topological sort will certainly be faster than Dijkstra. $\endgroup$
    – Kuifje
    Jun 13, 2021 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.