The shortest path with one resolvable edge

Question

I have this problem: "The shortest path with one resolvable edge. For a digraph bound to the edge, create the E*log(V) algorithm to find the shortest path from s to t , where you can change the weight of any one edge to zero. Suppose that the weights of the edges are non-negative. "

I don’t understand what they want from me. What does it mean to change the weight to zero? I think I can change any edge in any shortest path to zero, and it will still be the shortest.

Answer 1

First use Dijkstra to find the length S(v) shortest path from s to v for each vertex v . Then use Dijkstra to find the length T(v) shortest path from v to t for each vertex v . Then for each edge (v, w) find the sum S(v) + T(w) using the above rules. Finally, select the minimum path.

Note In this approach, we lose the weight of the edge (v,w) and find the shortest path through (v,w)

Answer 2

The problem is simple.

Suppose you have a shortest path with one resolvable edge, p = v1, ..., vi, vi + 1, ..., vm and (vi, vi + 1) is the missing edge
Obviously, the path (v1, ..., vi) is the shortest path between v1 and vi
and the path (vi + 1, ..., vm) is the shortest path between vi + 1 and vm
Define d (x, y) as the shortest path length between node x and node y
you can just find d (s, x) and d (x, t) for all node x using the dijkstra algorithm and now we have to select the skipped edges one at a time. In other words, the length of the shortest path with one missed edge is

min (d (s, u) + d (v, t)) for all edges (u, v) in the graph

and time complexity is O (E log V) due to Dijkstra's algorithm

Answer 3

The previous answers seem to suggest that Dijkstra gives the shortest distance from each vertex to each vertex, but this is not so.

If you run Dijkstra only once, starting with s, you have the shortest path from s to each vertex.

To find the shortest distance from each vertex to t, you need to run Dijkstra again, starting with t after reversing each edge of the graph.

Complete solution:

1) Run Dijkstra on graph G, starting with s, to get the shortest distance T (v) between s and any v.

2) Invert all the edges to get the inverse graph G '

3) Run Dijkstra on the graph G ', starting with t, to get the shortest distance R (v) between t and any v.

4) The missing edge is e (v1 → v2) for which T (v1) + R (v2) is minimal.

5) The path to the next is the concatenation of the shortest path between s and v1 given by the first Dijkstra, and the shortest path between v2 and t given by the second Dijkstra.

Answer 4

The existing answers are good and correct, but another idea that is more intuitive for me is to transform the chart and use a multi-level approach:

1. Create a copy of Count G and name it G'
2. For each edge (u, v) in G create an edge (u, v') directed from u (in G ) to v' (in G' ), with a weight of 0 .
3. Use any standard shortest path algorithm such as Dijkstra to calculate the shortest path from s to t' .

Answer 5

I came across this question when I was taking Princeton's Algorithm course on Coursera. I got the accepted answer, but I suggested an approach that I think should provide the shortest path with one missing edge from s to any other edge.

We will use the following class to store weighted information about directed edges:

 public class DirectedEdge implements Comparable<DirectedEdge> { private int from; private int to; private double weight; ... boilerplate stuff... 

However, we will also add a decorator class:

 public static class SkipPathEdge { DirectedEdge directedEdge; double longest; public SkipPathEdge(DirectedEdge directedEdge, double longest) { this.directedEdge = directedEdge; this.longest = longest; } } 

the longest here, representing the longest known segment of the shortest known path to the top.

The rest is a fairly standard Djikstra with an indexed queue with minimal priority and that’s all, but with a slightly modified relaxation method:

 private void relax(EdgeWeightedDigraph G, int e) { SkipPathEdge parentEdge = edgeTo[e]; for (DirectedEdge edge : G.adj(e)) { double longest = Math.max(parentEdge.longest, edge.getWeight()); double adjustment = longest - parentEdge.longest; SkipPathEdge childEdge = new SkipPathEdge(edge, longest); int from = edge.getFrom(), to = edge.getTo(); if (distTo[to] > distTo[from] + edge.getWeight() - adjustment) { distTo[to] = distTo[from] + edge.getWeight() - adjustment; edgeTo[to] = childEdge; if (minPQ.contains(to)) { minPQ.changeKey(to, distTo[to]); } else { minPQ.addKey(to, distTo[to]); } } } } 

And to clarify, we initialize edgeTo [s] as new SkipPathEdge(null, 0); so that we never have to deal with a null parent edge.

I think this should work if there isn’t something that I don’t think about.