How to find paths in the graph with strong links? 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?
 A: 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
$$
