The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient algorithm to construct an $n\times n$ matrix where the entry corresponding to vertices $u$ and $v$ is the minimum weight path consisting of exactly $\alpha$ edges, or $\infty$ if no such path exists? A path is a walk that does not repeat any vertices. Assume the vertices of $G$ are numbered as $v_1,\cdots, v_n$ so that the $(i,j)$th entry of the output matrix corresponds to the min weight walk between vertices $v_i$ and $v_j$.
I know how to solve the problem when vertices can be repeated using dynamic programming, but I can't seem to solve this particular problem because vertices might be distinct.
If I ignore the condition that each such path must use exactly $\alpha$ edges, then I think the following would work, but it might be inefficient: do a breadth-first search for every possible starting vertex $s$ to find the minimum weight walk from $s$ to all other vertices. I could then store these $n$ distances for each vertex to obtain the required $n\times n$ matrix (each computation would add a new row). This would take $O(n(n+m))$ time.
The problem with using exactly $\alpha$ edges is that even though one can decompose a shortest path of length $\alpha$ between two vertices $u$ and $v$ into a shortest path of length $\alpha_1$ between $u$ and $i$ and a shortest path of length $\alpha_2$ between $i$ and $v$ for some intermediate vertex $i$, where $\alpha_1 + \alpha_2 = \alpha$. But one must check that the shortest (min weight) path of length $\alpha_1$ doesn't share a vertex other than $i$ with the shortest path of length $\alpha_2$.
Correction: BFS obviously can't be used for the shortest paths of a weighted graph, but neither Dijkstra's nor Bellman ford can be used as no vertices can repeat.