<p>Summary:</p>
<ul>
<li><p>A dimension restriction is necessary.  Lemma 2 below observes that if <em>arbitrary</em> dimension is allowed the problem (even restricted to permutation matrices) is at least as hard as Graph Isomorphism (<a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems" rel="nofollow noreferrer">GI-hard</a>).</p>
</li>
<li><p>OP's problem (as restricted by OP to instances having constant dimension and matrices that either (i) all have at most one 1 per row, or (ii) all have at most one 1 per column) has a poly-time algorithm.</p>
</li>
</ul>
<hr />
<p>The upper bound we show is actually slightly stronger.
Given an instance of OP's problem,
let <span class="math-container">$\mathcal A$</span> denote the set of matrices labeling the edges.
Let <span class="math-container">$\mathcal A^*\vec c$</span> be the set of vectors obtainable
as products of the form <span class="math-container">$M_1 M_2 \cdots M_k \vec c$</span> for any <span class="math-container">$k\ge 0$</span>, with each <span class="math-container">$M_i\in \mathcal A$</span>.</p>
<p><strong>Lemma 1.</strong> <em>The problem has a poly(<span class="math-container">$|G|+|\mathcal A^*\vec c|)$</span>-time algorithm (with no restriction on the matrices or dimension).</em></p>
<p>For example, the following special cases are in P:</p>
<ul>
<li><p>If every edge has the identity matrix <span class="math-container">$I$</span>, then <span class="math-container">$\mathcal A^*\vec c=\{\vec c\}$</span>, so <span class="math-container">$|\mathcal A^*\vec c| = 1$</span>.  (This is the result shown in D.W.'s answer.)</p>
</li>
<li><p>If the matrices are (0,1) matrices, either all having at most one 1 in each column, or all having at most one 1 in each row,
then <span class="math-container">$|\mathcal A^*\vec c|\le |\mathcal A^*| \le n^n$</span>.
So when the dimension <span class="math-container">$n$</span> is constant (or even <span class="math-container">$O(\log(|G|)/\log\log |G|)$</span>) the algorithm
runs in time poly<span class="math-container">$(|G|)$</span>.</p>
</li>
</ul>
<hr />
<p><em>Proof sketch for Lemma 1.</em>
Given the digraph <span class="math-container">$G=(V,E)$</span>,
the algorithm computes <span class="math-container">$\mathcal A^*\vec c$</span>.
It then constructs a bigger edge-weighted digraph <span class="math-container">$G'$</span>
with a vertex <span class="math-container">$q(v, y)$</span>
for every pair <span class="math-container">$(v, y)$</span> in <span class="math-container">$V \times \mathcal A^*\vec c$</span>.
For every pair of vertices <span class="math-container">$q(v, y)$</span> and <span class="math-container">$q(v', y')$</span>,
there is an edge from the former to the latter
iff</p>
<ul>
<li><span class="math-container">$(v, v')$</span> is in <span class="math-container">$E$</span>, and</li>
<li><span class="math-container">$y = Ay'$</span>, where <span class="math-container">$A$</span> is the matrix labeling edge <span class="math-container">$(v, v')$</span>.</li>
</ul>
<p>If there is such an edge,
it is given (scalar) weight <span class="math-container">$\vec b\, \vec y'$</span>.</p>
<p>The algorithm then uses any standard shortest-path algorithm
to find the shortest path from any starting vertex in <span class="math-container">$G'$</span>
to the ending vertex in <span class="math-container">$G'$</span>,
where the starting vertices in <span class="math-container">$G'$</span>
are those of the form <span class="math-container">$q(u, y)$</span>
where <span class="math-container">$u$</span> is the starting vertex for OP's instance
and <span class="math-container">$y\in\mathcal A^*\vec c$</span>,
and the ending vertex is <span class="math-container">$q(v, \vec c)$</span>,
where <span class="math-container">$v$</span> is the ending vertex for OP's instance.</p>
<p>The idea for correctness is that any path
<span class="math-container">$q(v_1, y_1), q(v_2, y_2), \ldots, q(v_k, y_k=\vec c)$</span>
in <span class="math-container">$G'$</span>
from a starting vertex to the ending vertex
represents the path
<span class="math-container">$(v_1, v_2, \ldots, v_k)$</span> in <span class="math-container">$G$</span>
from the starting vertex <span class="math-container">$v_1$</span> to the ending vertex <span class="math-container">$v_k$</span> in <span class="math-container">$G$</span>.
The conditions for edges in <span class="math-container">$G'$</span>
guarantee that after this path traverses an edge
<span class="math-container">$(v_i, v_{i+1})$</span> labeled with some matrix <span class="math-container">$A$</span> and vector <span class="math-container">$\vec b$</span>,
it is the case that the product
<span class="math-container">$M_{i+1} M_{i+2} \cdots M_k \vec c$</span>
along the remainder of the path will equal <span class="math-container">$y_{i+1}$</span>.
Hence, (in <span class="math-container">$G)$</span> the vector <span class="math-container">$\vec b$</span> of the edge <span class="math-container">$(v_i, v_{i+1})$</span>
will contribute <span class="math-container">$\vec b y_{i+1}$</span> to the final cost,
just as the corresponding edge
(with weight <span class="math-container">$\vec b y_{i+1}$</span>) on the path in <span class="math-container">$G'$</span>
contributes to that path's final cost.
Thus, the cost of the path in <span class="math-container">$G'$</span>
will equal the cost of the corresponding path in <span class="math-container">$G$</span>.
<span class="math-container">$~~~~\Box$</span></p>
<hr />
<p><strong>Lemma 2.</strong> <em>The problem (restricted to permutation matrices,
but not constant dimension) is GI-hard.</em></p>
<p><em>Proof sketch for Lemma 2.</em> The proof is by a reduction from Graph Isomorphism (GI).
Given a GI instance <span class="math-container">$(G_1, G_2)$</span> of two undirected graphs, each (WLOG) with vertex set <span class="math-container">$[n]$</span>, and with the same number of edges, the reduction outputs the instance of OP's problem defined as follows.  (Note that here <span class="math-container">$n$</span> is the number of vertices in <span class="math-container">$G_1$</span>
and <span class="math-container">$G_2$</span>, not the dimension of an instance of OP's problem.
The instance of OP's problem produced by the reduction
will have dimension <span class="math-container">$n\choose 2$</span>.)</p>
<p>Let <span class="math-container">$U$</span> denote the set of possible edges
(i.e. unordered pairs of distinct vertices)
from vertex set <span class="math-container">$[n]$</span>.
So <span class="math-container">$|U| = {n\choose 2}$</span> and, for example,
the edge sets of <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>
are subsets of <span class="math-container">$U$</span>.</p>
<p>Let <span class="math-container">$\{0,1\}^U$</span>
represent the indicator vectors for such subsets of <span class="math-container">$U$</span>
in the standard way:
a given <span class="math-container">$x\in\{0,1\}^U$</span>
is identified with the edge set <span class="math-container">$E$</span> such that <span class="math-container">$x_e = 1$</span> iff <span class="math-container">$e\in E$</span>.</p>
<p>For <span class="math-container">$(u,v)\in U$</span>,
let <span class="math-container">$\pi(u, v)$</span> denote the permutation
induced on <span class="math-container">$U$</span> by exchanging the (names of the) vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span>.
That is, for every vertex <span class="math-container">$w\not\in \{u, v\}$</span>,
<span class="math-container">$\pi(u,v)$</span> swaps <span class="math-container">$(u, w) \in U$</span> with <span class="math-container">$(v, w)\in U$</span>,
leaving all other possible edges unchanged.</p>
<p>Let <span class="math-container">$\Pi = \{\pi(u, v) : (u,v)\in U\}$</span> denote the set of such permutations.  Note <span class="math-container">$|\Pi| = {n\choose 2}$</span>.</p>
<p>Now <span class="math-container">$G_1=([n], E_1)$</span> is isomorphic to <span class="math-container">$G_2=([n], E_2)$</span>
if and only if there is a sequence of
permutations in <span class="math-container">$\Pi$</span>
such that applying the sequence of permutations
to (the indicator vector <span class="math-container">$x(E_1) \in \{0,1\}^U$</span> of) <span class="math-container">$E_1$</span>
yields (the indicator vector <span class="math-container">$x(E_2) \in \{0,1\}^U$</span> of) <span class="math-container">$E_2$</span>.</p>
<p>Furthermore, there is a constant <span class="math-container">$c&gt;0$</span>
such that there is such a sequence
if and only if there is such a sequence of length
at most <span class="math-container">$cn \log n$</span>.</p>
<p>The reduction outputs a multi-digraph <span class="math-container">$D$</span>
with vertex set <span class="math-container">$[N]$</span> where <span class="math-container">$N=\lceil c n\log n\rceil$</span>
and, for each <span class="math-container">$i\in [N-1]$</span>,
there are <span class="math-container">$|\Pi|$</span> multi-edges from <span class="math-container">$i$</span> to <span class="math-container">$i+1$</span>,
with each such edge being labeled with the matrix for a (distinct) permutation in <span class="math-container">$\Pi$</span>.</p>
<p>Thus, the paths from <span class="math-container">$1$</span> to <span class="math-container">$N$</span> in <span class="math-container">$D$</span> correspond
to the sequences of permutations in <span class="math-container">$\Pi$</span>.
The start vertex <span class="math-container">$1$</span> is labeled
with (the starting) vector <span class="math-container">$x(E_1)$</span>.
The target vertex <span class="math-container">$N$</span> is labeled
with the vector <span class="math-container">$\vec c = -x(E_2)$</span>.
Then, the cost of taking a path from <span class="math-container">$1$</span> to <span class="math-container">$N$</span>
is (at most) <span class="math-container">$-|E_1| = -|E_2|$</span> iff
the sequence of permutations induced by the path,
applied to <span class="math-container">$x(E_1)$</span>, yields <span class="math-container">$x(E_2)$</span>.
Thus, this cost is achievable
if and only if <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are isomorphic.</p>
<p>(Note that if desired the multi-digraph <span class="math-container">$D$</span> can be converted
into an equivalent digraph using the standard
idea of replacing each edge <span class="math-container">$(i, j)$</span>
by a path <span class="math-container">$(i, v, j)$</span>,
where <span class="math-container">$v$</span> is a new artificial vertex, unique to the edge.)
<span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2024-02-28T18:08:45.077Z
why do you multiply $M_{i+1}\ldots M_k c$ should it be $ c M_k \ldots M_{i+1}$?
user1868607
CC BY-SA 4.0
2024-02-28T19:44:47.760Z
I see, yes, as you've defined $c$ that is probably right.  I was assuming the final cost would be calculated as $x c$ (as a matrix product, considering the two vectors as matrices, so equivalent to the the dot product), but I've probably got the dimensions of $c$ backwards.
Neal Young
CC BY-SA 4.0
2024-02-28T19:47:46.260Z
p.s. If I were going to implement this I would not construct the graph $G'$ explicitly, rather I would use an implicit definition (constructing vertices as encountered) and I would look for the path *backwards* in $G'$ (using the single target vertex in $G'$ as the source).  I would expect that to be more efficient in practice.
Neal Young
CC BY-SA 4.0
2024-02-21T02:03:19.453Z
2024-02-21T06:40:27.427Z
2024-02-21T06:40:27.427Z
Neal Young
<p>The usual rule is to ask only one question per post.  I'll answer the first, about <span class="math-container">$A=\text{Id}$</span>.  For that special case, the shortest path problem is easy to solve in polynomial time. I'll describe how to compute the (length of the) shortest path from a source node <span class="math-container">$s$</span> to a destination node <span class="math-container">$t$</span> in polynomial time.  You can then repeat this for all pairs <span class="math-container">$s,t$</span> if you wish.</p>
<p>Let the affine function at the target <span class="math-container">$t$</span> be <span class="math-container">$o= \vec{c} \vec{x} + d$</span>.  Note that <span class="math-container">$d$</span> is irrelevant (it does not affect which path is shortest) so WLOG we can take <span class="math-container">$d=0$</span>.  For any <span class="math-container">$\vec{x}$</span>, define <span class="math-container">$y=\vec{c} \vec{x}$</span>.  Then an update <span class="math-container">$\vec{x} := A \vec{x} + \vec{b}$</span> simplifies to <span class="math-container">$\vec{x} := \vec{x} + \vec{b}$</span> if <span class="math-container">$A=\text{Id}$</span>, and the effect on <span class="math-container">$y$</span> becomes <span class="math-container">$y := y + \vec{c} \vec{b}$</span>.</p>
<p>It follows that it suffices to track the effect on <span class="math-container">$y$</span>.  Thus, we have a standard shortest-path problem.  We replace each edge with update-operation <span class="math-container">$\vec{x} := \vec{x} + \vec{b}$</span> with an edge of length <span class="math-container">$\vec{c} \vec{b}$</span>.  Then, we look for the shortest path in the resulting transformed graph.  The shortest path in the transformed graph will also be the shortest path in the original graph.  Computing the shortest path in the transformed graph runs in polynomial time, so we obtain a polynomial-time solution to your problem when <span class="math-container">$A=\text{Id}$</span>.</p>

CC BY-SA 4.0
2024-02-20T18:38:54.123Z
2024-02-20T18:38:54.123Z
D.W.
<p>I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on <span class="math-container">$\mathbb{Q}$</span> as the problem of minimizing a rational value <span class="math-container">$x$</span> which is updated at each edge of the graph with the label <span class="math-container">$v$</span> of the edge. This we can write as <span class="math-container">$x:=x+v$</span>. The shortest path problem then becomes the problem of minimising the value of <span class="math-container">$x$</span>. This is known to be solvable in polynomial time.</p>
<p>Now suppose we generalise this to a constant number of variables <span class="math-container">$\vec{x}$</span>. We consider at each step an update of a vector <span class="math-container">$\vec{x} = A \vec{x} + \vec{b}$</span> where <span class="math-container">$A \in \mathbb{Q}^{n \times n}, \vec{b} \in \mathbb{Q}^{n \times 1}$</span>. The matrix <span class="math-container">$A$</span> and the vector <span class="math-container">$\vec{b}$</span> may be different at each edge. At the target node one computes an affine function <span class="math-container">$o = \vec{c} \vec{x} + d$</span> where <span class="math-container">$\vec{c} \in \mathbb{Q}^{n \times 1}$</span> and <span class="math-container">$d \in \mathbb{Q}$</span>. This target function may be different for each final node. The optimisation problem is to determine the minimal value of <span class="math-container">$o$</span>.</p>
<p>If we don't restrict the values of <span class="math-container">$A$</span> then the problem is strongly <span class="math-container">$NP$</span>-hard (<a href="https://cstheory.stackexchange.com/questions/53908/shortest-path-with-affine-updates-and-fixed-dimension">Shortest path with affine updates and fixed dimension</a>). I'm interested in the way to solve simpler problems. For instance,</p>
<ul>
<li><span class="math-container">$A = I$</span> the identity matrix.</li>
<li><span class="math-container">$A$</span> a 0/1-matrix with exactly one &quot;1&quot; per row.</li>
<li><span class="math-container">$A$</span> a 0/1-matrix with exactly one &quot;1&quot; per column.</li>
</ul>
<p>Is it known whether any of these problems for fixed <span class="math-container">$n$</span> is solvable in polynomial time?</p>

<ds.algorithms><np-hardness><shortest-path>
Shortest path with permutations and fixed dimension
user1868607
# Shortest path with permutations and fixed dimension

(Asked by: username_0 on 2024-02-20)

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with the label $v$ of the edge. This we can write as $x:=x+v$. The shortest path problem then becomes the problem of minimising the value of $x$. This is known to be solvable in polynomial time.

Now suppose we generalise this to a constant number of variables $\vec{x}$. We consider at each step an update of a vector $\vec{x} = A \vec{x} + \vec{b}$ where $A \in \mathbb{Q}^{n \times n}, \vec{b} \in \mathbb{Q}^{n \times 1}$. The matrix $A$ and the vector $\vec{b}$ may be different at each edge. At the target node one computes an affine function $o = \vec{c} \vec{x} + d$ where $\vec{c} \in \mathbb{Q}^{n \times 1}$ and $d \in \mathbb{Q}$. This target function may be different for each final node. The optimisation problem is to determine the minimal value of $o$.

If we don't restrict the values of $A$ then the problem is strongly $NP$-hard ([Shortest path with affine updates and fixed dimension](https://cstheory.stackexchange.com/questions/53908/shortest-path-with-affine-updates-and-fixed-dimension)). I'm interested in the way to solve simpler problems. For instance,

* $A = I$ the identity matrix.
* $A$ a 0/1-matrix with exactly one "1" per row.
* $A$ a 0/1-matrix with exactly one "1" per column.

Is it known whether any of these problems for fixed $n$ is solvable in polynomial time?

**Tags:** ds.algorithms, np-hardness, shortest-path


---

## 2 answers

### Answer by username_1 on 2024-02-21. Score: 3 | Accepted answer

Summary:

* A dimension restriction is necessary. Lemma 2 below observes that if *arbitrary* dimension is allowed the problem (even restricted to permutation matrices) is at least as hard as Graph Isomorphism ([GI-hard](https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems)).
* OP's problem (as restricted by OP to instances having constant dimension and matrices that either (i) all have at most one 1 per row, or (ii) all have at most one 1 per column) has a poly-time algorithm.

---

The upper bound we show is actually slightly stronger.
Given an instance of OP's problem,
let $\mathcal A$ denote the set of matrices labeling the edges.
Let $\mathcal A^\*\vec c$ be the set of vectors obtainable
as products of the form $M\_1 M\_2 \cdots M\_k \vec c$ for any $k\ge 0$, with each $M\_i\in \mathcal A$.

**Lemma 1.** *The problem has a poly($|G|+|\mathcal A^\*\vec c|)$-time algorithm (with no restriction on the matrices or dimension).*

For example, the following special cases are in P:

* If every edge has the identity matrix $I$, then $\mathcal A^\*\vec c=\{\vec c\}$, so $|\mathcal A^\*\vec c| = 1$. (This is the result shown in username_2's answer.)
* If the matrices are (0,1) matrices, either all having at most one 1 in each column, or all having at most one 1 in each row,
  then $|\mathcal A^\*\vec c|\le |\mathcal A^\*| \le n^n$.
  So when the dimension $n$ is constant (or even $O(\log(|G|)/\log\log |G|)$) the algorithm
  runs in time poly$(|G|)$.

---

*Proof sketch for Lemma 1.*
Given the digraph $G=(V,E)$,
the algorithm computes $\mathcal A^\*\vec c$.
It then constructs a bigger edge-weighted digraph $G'$
with a vertex $q(v, y)$
for every pair $(v, y)$ in $V \times \mathcal A^\*\vec c$.
For every pair of vertices $q(v, y)$ and $q(v', y')$,
there is an edge from the former to the latter
iff

* $(v, v')$ is in $E$, and
* $y = Ay'$, where $A$ is the matrix labeling edge $(v, v')$.

If there is such an edge,
it is given (scalar) weight $\vec b\, \vec y'$.

The algorithm then uses any standard shortest-path algorithm
to find the shortest path from any starting vertex in $G'$
to the ending vertex in $G'$,
where the starting vertices in $G'$
are those of the form $q(u, y)$
where $u$ is the starting vertex for OP's instance
and $y\in\mathcal A^\*\vec c$,
and the ending vertex is $q(v, \vec c)$,
where $v$ is the ending vertex for OP's instance.

The idea for correctness is that any path
$q(v\_1, y\_1), q(v\_2, y\_2), \ldots, q(v\_k, y\_k=\vec c)$
in $G'$
from a starting vertex to the ending vertex
represents the path
$(v\_1, v\_2, \ldots, v\_k)$ in $G$
from the starting vertex $v\_1$ to the ending vertex $v\_k$ in $G$.
The conditions for edges in $G'$
guarantee that after this path traverses an edge
$(v\_i, v\_{i+1})$ labeled with some matrix $A$ and vector $\vec b$,
it is the case that the product
$M\_{i+1} M\_{i+2} \cdots M\_k \vec c$
along the remainder of the path will equal $y\_{i+1}$.
Hence, (in $G)$ the vector $\vec b$ of the edge $(v\_i, v\_{i+1})$
will contribute $\vec b y\_{i+1}$ to the final cost,
just as the corresponding edge
(with weight $\vec b y\_{i+1}$) on the path in $G'$
contributes to that path's final cost.
Thus, the cost of the path in $G'$
will equal the cost of the corresponding path in $G$.
$~~~~\Box$

---

**Lemma 2.** *The problem (restricted to permutation matrices,
but not constant dimension) is GI-hard.*

*Proof sketch for Lemma 2.* The proof is by a reduction from Graph Isomorphism (GI).
Given a GI instance $(G\_1, G\_2)$ of two undirected graphs, each (WLOG) with vertex set $[n]$, and with the same number of edges, the reduction outputs the instance of OP's problem defined as follows. (Note that here $n$ is the number of vertices in $G\_1$
and $G\_2$, not the dimension of an instance of OP's problem.
The instance of OP's problem produced by the reduction
will have dimension $n\choose 2$.)

Let $U$ denote the set of possible edges
(i.e. unordered pairs of distinct vertices)
from vertex set $[n]$.
So $|U| = {n\choose 2}$ and, for example,
the edge sets of $G\_1$ and $G\_2$
are subsets of $U$.

Let $\{0,1\}^U$
represent the indicator vectors for such subsets of $U$
in the standard way:
a given $x\in\{0,1\}^U$
is identified with the edge set $E$ such that $x\_e = 1$ iff $e\in E$.

For $(u,v)\in U$,
let $\pi(u, v)$ denote the permutation
induced on $U$ by exchanging the (names of the) vertices $u$ and $v$.
That is, for every vertex $w\not\in \{u, v\}$,
$\pi(u,v)$ swaps $(u, w) \in U$ with $(v, w)\in U$,
leaving all other possible edges unchanged.

Let $\Pi = \{\pi(u, v) : (u,v)\in U\}$ denote the set of such permutations. Note $|\Pi| = {n\choose 2}$.

Now $G\_1=([n], E\_1)$ is isomorphic to $G\_2=([n], E\_2)$
if and only if there is a sequence of
permutations in $\Pi$
such that applying the sequence of permutations
to (the indicator vector $x(E\_1) \in \{0,1\}^U$ of) $E\_1$
yields (the indicator vector $x(E\_2) \in \{0,1\}^U$ of) $E\_2$.

Furthermore, there is a constant $c>0$
such that there is such a sequence
if and only if there is such a sequence of length
at most $cn \log n$.

The reduction outputs a multi-digraph $D$
with vertex set $[N]$ where $N=\lceil c n\log n\rceil$
and, for each $i\in [N-1]$,
there are $|\Pi|$ multi-edges from $i$ to $i+1$,
with each such edge being labeled with the matrix for a (distinct) permutation in $\Pi$.

Thus, the paths from $1$ to $N$ in $D$ correspond
to the sequences of permutations in $\Pi$.
The start vertex $1$ is labeled
with (the starting) vector $x(E\_1)$.
The target vertex $N$ is labeled
with the vector $\vec c = -x(E\_2)$.
Then, the cost of taking a path from $1$ to $N$
is (at most) $-|E\_1| = -|E\_2|$ iff
the sequence of permutations induced by the path,
applied to $x(E\_1)$, yields $x(E\_2)$.
Thus, this cost is achievable
if and only if $G\_1$ and $G\_2$ are isomorphic.

(Note that if desired the multi-digraph $D$ can be converted
into an equivalent digraph using the standard
idea of replacing each edge $(i, j)$
by a path $(i, v, j)$,
where $v$ is a new artificial vertex, unique to the edge.)
$~~~\Box$

> **Comments:**
> **username_0**: why do you multiply $M_{i+1}\ldots M_k c$ should it be $ c M_k \ldots M_{i+1}$?  
> **username_1**: I see, yes, as you've defined $c$ that is probably right.  I was assuming the final cost would be calculated as $x c$ (as a matrix product, considering the two vectors as matrices, so equivalent to the the dot product), but I've probably got the dimensions of $c$ backwards.  
> **username_1**: p.s. If I were going to implement this I would not construct the graph $G'$ explicitly, rather I would use an implicit definition (constructing vertices as encountered) and I would look for the path *backwards* in $G'$ (using the single target vertex in $G'$ as the source).  I would expect that to be more efficient in practice.  

---

### Answer by username_2 on 2024-02-20. Score: 2

The usual rule is to ask only one question per post. I'll answer the first, about $A=\text{Id}$. For that special case, the shortest path problem is easy to solve in polynomial time. I'll describe how to compute the (length of the) shortest path from a source node $s$ to a destination node $t$ in polynomial time. You can then repeat this for all pairs $s,t$ if you wish.

Let the affine function at the target $t$ be $o= \vec{c} \vec{x} + d$. Note that $d$ is irrelevant (it does not affect which path is shortest) so WLOG we can take $d=0$. For any $\vec{x}$, define $y=\vec{c} \vec{x}$. Then an update $\vec{x} := A \vec{x} + \vec{b}$ simplifies to $\vec{x} := \vec{x} + \vec{b}$ if $A=\text{Id}$, and the effect on $y$ becomes $y := y + \vec{c} \vec{b}$.

It follows that it suffices to track the effect on $y$. Thus, we have a standard shortest-path problem. We replace each edge with update-operation $\vec{x} := \vec{x} + \vec{b}$ with an edge of length $\vec{c} \vec{b}$. Then, we look for the shortest path in the resulting transformed graph. The shortest path in the transformed graph will also be the shortest path in the original graph. Computing the shortest path in the transformed graph runs in polynomial time, so we obtain a polynomial-time solution to your problem when $A=\text{Id}$.


---

