Un camino está definido como una sucesión de vértices adyacentes, así que tu pregunta no tiene sentido porque no hay "caminos" entre dos aristas.
Y explica mejor lo de "como saber los caminos". No sé si te refieres al número de caminos de una longitud determinada, al camíno minimo entre estos, o a qué.
Pues haces la matriz de adyacencia A, calculas la potencia n-ésima y el elemento (A^n)^i_j es el número de caminos de longitd n entre los vértices i, j del grafo que tiene a A como matriz de adyacencia.