1
$\begingroup$

I have a directed weighted multigraph whose vertices are sets of URLs.

We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are vertices of the graph.

Now having a set of source vertices and destination vertices, I need to find the minimum weight path (or several paths, if there are several such paths of the same weight) from a source to a destination of nonzero length and having at least one edge not of the form $i\to j$ where $i\subset j$.

Also it is desirable that the paths do not have adjanced edges of the form $i\to j$ where $i\subset j$.

I am currently working with Python and NetworkX.

I think (but not sure), that we can assume that the set of source vertices is disjoint with the set of destination vertices.

Improve this question
$\endgroup$
1
$\begingroup$

You can solve this in $O(|E| \log |V|)$ time, if all weights are non-negative. Basically, you'll build a larger graph, of twice the size, then do a shortest-paths query in this graph.

I will call the edges of the original multigraph regular and added edges of the form $i\to j$ for $i\subset j$ as irregular.

For each set $i$, you have two vertices $i^-,i^+$ in the new graph, where $i^-$ represents a step along the path that visits set $i$ before visiting any regular edge; and $i^+$ represents a step along the path after visiting a regular edge. It is easy to work out the edges in this graph (if you have an irregular edge $i \to j$ in the original graph, you have $i^- \to j^-$ and $i^+ \to j^+$; if $i \to j$ is a regular in the original graph, you have $i^- \to j^+$ and $i^+ \to j^+$).

Add a source node $s$ to this large graph, with an edge $s \to i^-$ for each $i$ in your set of source vertices; and similarly add a sink node $t$ with an edge $i^+ \to t$ for each sink vertex $i$.

Finally, find the shortest path from $s$ to $t$ in this bigger graph using any standard algorithm for shortest paths (e.g., Dijkstra's algorithm).

You can accommodate the restriction about adjacent edges by doubling the size of the graph again. I'll let you work out the details. Basically, each vertex in the bigger graph represents a vertex in the original graph, plus a little bit of state summarizing everything you need to know about what comes before this on the path.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry, I don't understand you. You speak about visiting $i$ before visiting $i\subset j$ and after visiting such an edge. But what about the remaining case if $i$ is visited neither before nor after an edge of the form $i\subset j$? $\endgroup$ – porton Aug 18 '18 at 2:40
  • $\begingroup$ Or do you mean before/after visiting it in at least one element of the entire path? $\endgroup$ – porton Aug 18 '18 at 2:41
  • $\begingroup$ It seems to make sense to flip from $-$ to $+$ when encountering an edge not of the form $i\subset j$. Don't you mean this? (with "not") $\endgroup$ – porton Aug 18 '18 at 2:43
  • $\begingroup$ @porton, you're right! Flip the cases. I've edited the answer accordingly. Thanks for the careful reading. As for the first comment, by "before" I meant "haven't visited such an edge yet (at this stage in the traversal)" and by "after" I meant "have". So, that covers all the possible cases. Hope that makes sense. Sorry if this is confusing or hard to follow. $\endgroup$ – D.W.♦ Aug 18 '18 at 4:50
  • $\begingroup$ I've edited the answer to correct errors. $\endgroup$ – porton Aug 18 '18 at 15:57

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.