# Does Dijkstra's algorithm find the optimal solution for a weighted and directed shortest paths problem?

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.

• 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. Jun 13, 2021 at 8:45
• Could you describe the problem more in detail ("some other constraints should be satisfied too")? Or give an example ? Jun 13, 2021 at 13:35
• @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. Jun 13, 2021 at 15:16
• @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).
– prubin
Jun 13, 2021 at 19:17