Counting the directed paths in a particular directed graph /runtime My question is:
 How much time does a computer need, who compares the length of $10^9$ different paths within a second, to find the shortest way  in the following graph $ G=(V,E)$ for n=100.
$$\begin{align}
V=&\{s, v_1, v_2,\ldots, v_n, t\}, \quad n=2k, k \in \mathbb{N} \\
E=&\{ (s, v_1), (s, v_2), \\
&\;(v_1,v_3), (v_1,v_4), (v_2,v_3),(v_2,v_4), \\
&\;(v_3,v_5), (v_3,v_6), (v_4,v_5), (v_4,v_6), \\
&\;\ldots, \\
&\;(v_{n-5},v_{n-3}), (v_{n-5},v_{n-2}), (v_{n-4},v_{n-3}), (v_{n-4},v_{n-2}), \\
&\;(v_{n-3},v_{n-1}), (v_{n-3},v_{n}), (v_{n-2},v_{n-1}), (v_{n-2},v_{n}), \\
&\;(v_{n-1},t), (v_{n},t) \}
\end{align}$$

I would say:  $\frac{2^{100}}{10^9}$ Am I right?
 A: The answer depends on what and how the computer have to find. In real applications computers are wisely guided in order to reduce the number of possibilities to check. It very lucky cases it can turn our that there is no need to write a program, because the solution is already found by hand. For instance, for any two vertices $v_i$ and $v_j$ of $G$ (here we put $s=v_0$ and $t=v_{2k}$) we can easily provide a shortest path between $v_i$ and $v_j$, if $i<j$ (if $i>j$ then there are no path from $v_i$ to $v_j$).
If we wish computer to find shortest paths from a given vertex $v$ to all other vertices in the graph,  the known algorithms are rather fast,  even in the weighted case.
If the computer have to check all paths between two fixed vertices $v$ and $u$ then the number of the paths depends on $v$ and $u$. For instance, as easy to see, each path from $s$ to $t$ has length $k+1$ and there are exactly $2^k$ of them (this hold because at each vertex distinct from $t$ there is exactly two possibilities to choose a direction, and any such a choice leads towards $t$).
