find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)

Question

We have a weighted and undirected graph. I want to find the shortest path between two vertices with Dijkstra algorithm. But in the path, the weight of the edges should be increased and decreased one by one. For example, in the below graph, the answer is the third path:

My idea: Remove the paths that do not meet the condition of the problem and then find the shortest paths with Dijkstra. But I don't know how to remove a path from Dijkstra's check without removing that edge (because one edge may participate in several paths) Or is there a better way for this problem?

Answer 1

If I understand you correctly, it seems like the solution is to simply skip the frontier nodes that does not conform to the condition you have described.

My idea: Remove the paths that do not meet the condition of the problem and then find the shortest paths with Dijkstra

I think you're on the right direction. To be more concrete, if you have a frontier node $n$, with parent node $x$ and child node $y$, and the cost function $C(a, b)$ denotes the cost of the path between nodes $a$ and $b$, and if $i$ represents the depth of node $n$, then you should remove node $n$ if

$$ \begin{array}{c l} C(x, n) <= C(n, y) & \quad \textrm{if } i \textrm{ is odd} \\ C(x, n) >= C(n, y) & \quad \textrm{otherwise} \end{array} $$

You may want to think about the scenario if the pattern starts with a decrease from the starting node to its child node, instead of an increase like the examples shown in your question. Think also about the edge cases: what if $n$ is the root node? How do you take that into account for the cost function $C$?