0
$\begingroup$

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: enter image description here

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?

$\endgroup$
2
  • $\begingroup$ Your explaination is a bit confusing. Do you mean that you are searching for paths with edge weights alternatingly increasing and decreasing along the path? $\endgroup$
    – Nathaniel
    Jan 18, 2023 at 22:50
  • $\begingroup$ Yes. Looking for the shortest paths that have such conditions. $\endgroup$
    – Amir
    Jan 19, 2023 at 2:28

1 Answer 1

1
$\begingroup$

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$?

$\endgroup$

Your Answer

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

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