New answers tagged shortest-path
0
To decide if there is a path in $O(N)$ for a $N$ cells maze , you can simply run a BFS from start (As ryan already said, here, one should not talk of Dijkstra meaning priority queue...). So if you can reach both, the waypoint and the exit, it exists a solution.
Proof
You already proved that on a simple path, there is no need to consider the re-orientation of ...
1
I guess this is another non-answer.
$k$ waypoints $\in \mathrm{NP\ hard}$
The generalization of this problem ($k$ waypoints) is NP-hard even without turnstiles.
The reduction can be seen in Amiri et al. [1] from subset traveling salesman problem (TSP):
In the subset TSP, the task is to find a shortest closed walk that visits a given subset of vertices [38]....
2
There is a theorem that can be used to characterize the optimal solution, which then makes algorithm design trivial. In particular, you can solve the problem in logarithmic time.
Theorem
Suppose we are hoping for a solution that uses $k$ time steps. Let $v_0$ denote the starting velocity vector, $s$ the starting position, and $t$ the target position. Let $...
0
Thanks to @nirshahar for pointing out the data structure is Fibonacci heap with a worst case running time of O(a + b log n) where a = number of inserts, b = number of deletions, n = maximum size of the heap. For Dijkstra's algorithm for shortest path we have to insert M number of edges initially followed by n number of deletions in each iteration. Hence it ...
2
Update: I'm accepting my own answer for now. If anyone want to make an answer with the full proof, I'll glady accept it.
Short answer: Encode the maze as a directed graph and apply your usual Dijkstra or A*, ignoring the state you leave the turnstiles in. The turnstiles can be encoded by having arcs both ways on the sides without bar, and only the out going ...
3
This is not an answer, but also too many words for a comment and I didn't want to post a handful of comments.
I am not sure if this is NP-hard or not, but I have some ideas for a proof.
Proving NP-hard
I would take an approach similar to the NP-hardness proof for Super Mario Bros. Please watch this lecture: https://youtu.be/7d73E1DiH0w?t=2851
First you ...
1
Let $D(t,i)$ denote the length of the shortest among the path from $s$ to $t$ in $G$ that use at most $i$ edges.
We will focus on the generic $i$-th iteration of the algorithm and show that:
(i) after all the edges in $E_1$ have been considered, we must have $d(t) \le D(t, 2i)$ for each vertex $t \in R$.
(ii) after all the edges in $E_2$ have been ...
2
When all edges have weight 2 and $n = |V|$ the problem is equivalent to longest path which is NP-complete. So unless P = NP, there is no efficient algorithm for solving the problem.
Top 50 recent answers are included
