6
$\begingroup$

Given a weighted graph including two nodes $s$ and $t$, some edges can be removed without changing the shortest path from $s$ to $t$. Maybe there is an edge in the graph that, if that edge is removed, the path between $s$ and $t$ doesn't exist anymore.

Describe an efficient algorithm that selects the edge, that if that edge is deleted the length of the shortest path from $s$ to $t$ increases the most (so i.e. it goes from $2$ to $10$).

So it is obvious that I need to delete an edge that is used in the shortest path from $s$ to $t$.

Of course I could delete an edge that is part of the shortest path from $s$ to $t$, then again find the shortest path. I do this for every edge that is in the shortest path and then compare the all the new shortest paths. But this takes way too much time, and it isn't a really efficient algorithms and it isn't mathy.

It is some kind of reverse shortest path algorithm? Could somebody give me a few tips?

$\endgroup$
  • $\begingroup$ Are all edge weights positive? $\endgroup$ – Mike Pierce Sep 16 '15 at 3:50
  • $\begingroup$ Yes, all edge weights positive. Sorry I didnte state that. $\endgroup$ – user3302735 Sep 16 '15 at 9:28
  • 1
    $\begingroup$ It depends on what you mean by "efficient". In my world, efficient means "in polynomial time", so I'd consider your solution efficient. And it's mathy enough for me. So, do you have a precise meaning for 'efficient' ? $\endgroup$ – Manuel Lafond Sep 16 '15 at 18:05
  • $\begingroup$ Hahaha, thats a very good question. In my book it says that an algorithm is considered efficient if the calculation time is limited by a certain polynomial. So I guess the algorithm is considered efficient? But what if I want to make it even more efficient? $\endgroup$ – user3302735 Sep 16 '15 at 18:53
1
$\begingroup$

I would first compute the shortest $s$-$t$-path $P_{st}$. For nodes $u$ and $v$ in this path let $d(u,v)$ denote the shortest path distance from $u$ to $v$. This distance can be read from $P_{st}$ since the shortest $u$-$v$-path must be contained inside $P_{st}$.

Remove all edges of $P_{st}$ from the graph. In the modified graph run an all pairs shortest path algorithm to obtain distances $d'(u,v)$ for all nodes $u$ and $v$. For all nodes $u$ inside $P_{st}$ compute \begin{align*} D(u) = \min_{v \in P_{st}} d(s,u) + d'(u,v) + d(v,t) \end{align*} This value tells you the length of shortest $s$-$t$-path if edge $(u,u') \in P_{st}$ is removed from the graph. Note that $u'$ is the next node after $u$ in $P_{st}$ and is not necessarily identical to the node $v$ which achieves the minimum.

I guess this is not yet as mathy as you would prefer, however at least you do not obviously enumerate all solutions (though, in principle you still do).

$\endgroup$
0
$\begingroup$

A variant of Dijkstra's algorithm should do it. You can combine your search for "shortest path without using edge $e$" with your search for the shortest path overall. To do so, maintain a table where you record, for each edge $e$, the shortest path that avoids using edge $e$. The algorithm is as follows.

  1. Initialize a list CUTS to be the set of all edges in the graph.

    Initialize a table CUT-PATH-LENGTH, associating each edge $e$ with the length of the shortest path from the start to the goal that avoids edge $e$. These values are all initially $\infty$, indicating that no path has been found at all.

    Initialize SHORTEST-PATH-OVERALL to null.

    Initialize an AGENDA containing the initial singleton path.

  2. While the agenda is not empty and the CUTS list is not empty:

    1. Remove the first path from the agenda.

    2. If that path leads to the goal, compute its length $\ell$. For every edge $e$ in CUTS, excluding edges in the path, set the entry CUTS-PATH-LENGTH[$e$] = $\ell$. Then remove $e$ from CUTS.

      If this was the first time a path to the goal was found, it's the shortest path overall. Store it as SHORTEST-PATH-OVERALL.

    3. Compute all loopless one-edge extensions of the path. Add them to the agenda, then sort the agenda in increasing order of length.

  3. When the loop terminates, the shortest path (as well as its remove-one-edge runner-ups) are stored in the table CUT-PATH-LENGTH.

    If SHORTEST-PATH-OVERALL was not found, then the start and end node are actually disconnected to begin with. Removing an edge won't make a difference.

    If SHORTEST-PATH-OVERALL was found, then for each edge $e$ in the path, the entry CUT-PATH-LENGTH[$e$] records the length of the shortest path between the start and end nodes when edge $e$ is removed. Find the edge corresponding to the largest such value and return it.

    (In particular: if the loop terminated while CUTS was non-empty, then removing any edge in CUTS causes the start and end nodes to become disconnected, so you can immediately return any one of those edges.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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