I am trying to find the longest path in a directed graph using matrices. Let's assume this matrix is given. For example, from point 1 I can get to point 4 and 5 as you can see in the second row of the table. I know there are some algorithms out there that can solve this issue but they seem to be very complex. I was told it is possible to do it relatively simple with matrix multiplication in excel. But I have no idea how. Is it even possible? What approach would you use?
The graph looks like:
On
This is a directed acyclic graph (DAG). That is, once a path leaves some vertex, it will never return to to that vertex. There is a well-known algorithm to find a longest path in a graph, using topological sort.
It is possible to find the length of a longest path using matrix multiplication in excel, but I don't see how to find the path itself, without some additional work.
You've constructed the correct matrix, $A=(a_{ij})$, where $a_{ij}=1$ if and only if $ij$ is an edge. Now if we compute $B=(b_{ij})=A^2$, then $$b_{ij} =\sum_{k=1}^n a_{ik}a_{kj},$$ and we see that $b_{ij}>0$ if and only if there is some vertex $k$ such that both $ik$ and $kj$ are edges, so that there is a path of length two from $i$ to $j$. We can continue in this manner, and the nonzero elements of $A^m$ will show which pairs of vertices have paths of length $m$ between them.
This process must stop, since no path can visit a vertex twice. The maximum path length is $\ell$ if $A^\ell\neq0$ and $A^{\ell+1}=0$.
This doesn't produce the path, but if we look at $A^\ell$, we can find the initial and terminal vertices, say $\alpha$ and $\omega$, of a path of maximum length. Now for each vertex $v_1$ such that $\alpha v_1$ is an edge, we look at $A^{\ell-1}$ to see if there is a path from $v_1$ to $\omega$. Only those $v_1$ with such path merit consideration as the second vertex on the path. Then for each such candidate $v_1$, and each of its successor vertices $v_2$, look for a path from $v_2$ to $\omega$ in $A^{\ell-2}$, and so on. For a graph as small as the one in this example, it would be easier to find the path from the diagram, once you know $\alpha$ and $\omega.$
Personally, I think the algorithm based topological sort is easier, even by hand, although there is a little bit to learn at the outset.
In general, if $A$ is the adjacency matrix of a (directed) graph, $A^k_{u,v}$ is the number of (directed) walks of length $k$ from $u$ to $v$.
In general, that doesn't say much useful about paths. But in this specific digraph, you could compute $A^6$ to be the zero-matrix. This also means that there must be no directed cycle in the graph, so walks and paths happen to be the same thing in this digraph. Then you can note that $A^5$ has exactly one non-zero entry which represents a path of length 5 from 2 to 7.
I strongly recommend against using matrix multiplication to actually construct a directed path even when you know one exists, because I'm not sure it gives as much information compared to its inefficiency compared with other algorithms. In such a small case, it's obviously far easier to trace it out with your finger.