1
$\begingroup$

I have a directed graph with non-negative weights on the edges. I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300). I want to collect all the shortest paths from x in X to y in Y.

The weight of the edges depend on the previous edge in the path I am currently on. enter image description here

Testing the possible paths between x1 and y1, e4 has same attribute "B" as the preceding edge e3, so its weight will be reduced (I want to favour paths with same properties).

How do I actually find the shortest among the paths among x1 and y1 in this scenario?

$\endgroup$
  • $\begingroup$ Is the penalty the same for all switches between edges of different types? It would be helpful to elaborate on how the weight changes work exactly in your case. $\endgroup$ – Mikhail Tikhomirov Sep 17 '17 at 20:42
  • $\begingroup$ The obvious answer is split e1 and (another edge that points to the same node) to point at different nodes, both of which then both point to the same nodes. Depending on what your graph looks like, this could explode. It also depends on how exactly the edge weight depends on previous edges. Could you tell us more about that? $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 17 '17 at 21:31
  • $\begingroup$ I was thinking about dividing the weight by a constant factor, identical for each edge, e.g. whenever I am using an edge with same property as the previous one, divide its weight by 2. $\endgroup$ – Gaia Sep 18 '17 at 6:53
1
$\begingroup$

Let your graph be $G=(V,E)$. Build a new graph $G'=(V',E')$, where each vertex in $G'$ corresponds to a pair $(u,v)$ of vertices in $G$. Add an edge $(u,v) \to (v,w)$ in $G'$ iff there is an edge $v \to w$ in $G$. The intended meaning of the vertex $(u,v)$ is that you are currently at vertex $v$ in $G$, and previously were at vertex $u$. Thus, you can now figure out what weight to put on the edge $(u,v) \to (v,w)$ -- namely, whatever weight you want to put on the edge $v \to w$ assuming you previously traversed the edge $u \to v$.

Let $X' = \{(x,u) \in E : x \in X, u \in V\}$ and $Y' = \{(u,y) \in E : u \in V, y \in Y\}$. Now, the find the shortest path in $G'$ from each vertex in $X'$ to each vertex in $Y'$, using an all-pairs shortest paths algorithm. From this you can infer the length of the shortest path in $G$ from some vertex in $X$ to some vertex in $Y$, while taking into account the fact that edges switch weights.

If you use the Floyd-Warshall algorithm, the running time will be $O(|V'|^3)$, which is at most $O(|V|^6)$. As an optimization, the vertex set $V'$ can be taken to be $V' = \{(u,v) : u,v \in V, (u,v) \in E\}$. Then the running time of Floyd-Warshall in $G'$ will be at most $O(|E|^3)$. Given that your original graph $G$ is fairly small, this might already be feasible without further optimizations.

If you want further optimizations, here's one more. You can add to $G'$ a special vertex $x^*$ for each $x \in X$, with an edge $x^* \to (x,u)$ in $G'$ for each $(x,u) \in E$ with the same weight as the edge $x \to u$ in $G$; and similarly add $y^*$ for each $y \in Y$, with edge $(u,y) \to y^*$ of weight 0. Now find the shortest path from each $x^*$ to each $y^*$. This can be done by applying Dijkstra's algorithm $|X|$ times, once for each $x \in X$, to find the distance from $x^*$ to each other node in the graph. The total running time will be $O(|X| \cdot |E'| \log |V'|)$, which is $O(|X| \cdot |V| \cdot |E| \log |V|)$. You can also achieve running time $O(|Y| \cdot |V| \cdot |E| \log |V|)$ by searching backwards (e.g., reversing the graph). Given that you have $|Y| \approx 300$, $|V| \approx 2000$, and $|E| \le |V|^2 = 4000000$, this might complete rapidly.

$\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.