Finding a minimum weight path with certain restrictions 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.
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.