I have a directed graph $G = (V, E)$ which is not necessarily fully connected, where $V,E$ denote vertices and edges of $G$. Also an adjacency matrix $A$ represents the weights of directed edges in $G$, i.e. $a_{ij}$ means the weight of the edge from verice $i$ to $j$ and $a_{ij}$ is real number in range $[0~1]$.
Assuming each $a_{ij} \leq 1$, i'm interested in finding paths in $G$ for which the average weight of the path is close to $1$. In other words, the path includes edges with weights close to $1$.
Instead of doing a loop(s) of brute-force search in $G$, is there any systematic way to handle this problem?
Also, should i choose the path length $k$ in advance?
You could do this with linear programming:
Define binary variables $x_{ij}$ that take value $1$ if edge $(i,j)$ is used in the path and solve the following optimization problem : $$ \mbox{Min }\; z $$ subject to:
\begin{align} &sink_i+\sum_{j}x_{ij} = \sum_{j}x_{ji} + source_i\quad &\forall i\in V\\ &z \ge \varepsilon_{ij}\quad &\forall i,j\in V \\ & x_{ij}- \varepsilon_{ij} \le a_{ij}x_{ij} \quad &\forall i,j\in V \\ &\sum_{i} source_i =1 \\ &\sum_{i} sink_i =1 \\ &\varepsilon_{ij} \ge 0 \quad &\forall i,j\in V \\ &source_i, sink_i \in \{0,1\} \quad &\forall i\in V \end{align}
The first set of constraints are flow balance constraints (what goes in must go out). With the third constraint, you impose that the difference between the weight of an edge $(i,j)$ on a path and $1$ is bounded by $\varepsilon_{ij}$. The second constraint defines $z=\max\{\varepsilon_{ij}\}$. And since you minimize $z$, you should end up with a path with weights close to $1$.
As an example, if edge $(i,j)$ is not in the path, then $x_{ij}=0$, and the third constraint is : $$ 0- \varepsilon_{ij} \le 0 $$ which leads to $\varepsilon_{ij}=0$. If edge $(i,j)$ is in the path, then $x_{ij}=1$, and the third constraint is : $$ 1- \varepsilon_{ij} \le a_{ij} $$ which bounds the difference between $a_{ij}$ and $1$ by $\varepsilon_{ij}$.
If you need a specific path length $k$, it is also easy to handle with this approach (just add $\sum_{i}\sum_{j}x_{ij}\{=,\ge\}k$ in the constraints). Note that without a given path length, a trivial solution is any edge with weight $a_{ij}=1$.
You might (I am not $100\%$ sure) need to add a constraint like $$ \sum_{j}x_{ji}\le M(1-source_i) \quad \forall i \in V $$ to make sure that no unit of flow enters the source. And similarly with the sink, you don't want any edges of the path starting from the sink: $$ \sum_{j}x_{ij}\le M(1-sink_i) \quad \forall i \in V $$