8

Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). ...


4

Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need. Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$. Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)


3

An alternative (but essentially equivalent to @SamWestrick's) way of thinking about it is to run Dijkstra on the original graph but keeping track of two parameters for each vertex: the shortest path with an even number of red edges found so far, and the shortest with an odd number. Here's a more precise description of the algorithm. For each vertex $v$, ...


3

We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with ...


3

Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A \rightarrow C \...


2

I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods: Dijkstra algorithm is an exploration method that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the ...


2

Dijkstra's already does follow the shortest pah found so far to one of the remaining nodes at each step. I think your confusion lies in the "enqueue each neighbor of the current node" step: we can't just follow the shortest one of these to get the next node because the next shortest path might not be to a neighbor of the current node. Thus we enqueue it as ...


2

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm. However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article We now need to pick a new ...


1

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s. The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges). Same with the log factors, ...


1

Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$. Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given ...


1

In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}[u]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}[u]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$. The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's ...


1

If you check what Dijkstra's algorithm does, it computes the shortest paths to all nodes from a given start node.


1

One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$). So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the ...


Only top voted, non community-wiki answers of a minimum length are eligible