How to Model Path Being Only Through Adjacent Cells

Question

I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real life on a physical space. I would like to generate a continuous path from cell A to cell B. One constraint that I would like to add is that the solution must be such that the path is only made of transitions between physically adjacent cells. That means no diagonal (or orthogonal) skips over any cells. Only stepping from a cell to its 4 adjacent cells and so on.

How do I add this as a constraint in my problem?

An idea that I had was to make the weight of edge from Cell X to any cell that is not adjacent as infinity, but that seems like a hack in implementation more than a proper constraint.

EDIT: I will be implementing this model using Google OR-Tools, and the weight of all the edges will be elements of an adjacency matrix. Therefore, every possible edge will be a part of the matrix, and hence omiting edges entirely to constraint the solution is not possible. Original question still stands: how can I add this feature of the problem as a constraint?

Answer 1

A standard approach for modeling a path from source $s$ to sink $t$ in a directed graph with node set $N$ and arc set $A$ is to let continuous variable $x_{ij} \ge 0$ represent the flow along the arc $(i,j)$ from node $i$ to node $j$ and impose flow-balance constraints $$\sum_{(i,j)\in A} x_{ij} - \sum_{(j,i)\in A} x_{ji} = \begin{cases} 1 & \text{if $i=s$}\\ -1 & \text{if $i=t$}\\ 0 &\text{if $i\in N \setminus \{s,t\}$} \end{cases} $$ that send one unit of flow from $s$ to $t$. Rather than imposing some large penalty on inadmissible arcs, just omit them from $A$.