Aqui está o exercício:

Seja v e w dois vértices em um grafo direcionado G = (V, E). Projete um algoritmo de tempo linear para encontrar o número de diferentes caminhos mais curtos (não necessariamente vértice disjunto) entre v e w. Nota: as arestas em G são não ponderadas

Para este imposto, eu resumir da seguinte forma:

É um gráfico direcionadoEle pedeo número de diferentes caminhos mais curtos. Primeiro, os caminhos devem ser mais curtos, então pode haver mais de um desses caminhos mais curtos cujo comprimento é o mesmo.entre v e w, então ambos, de v para we de w para v, devem ser contados.tempo linear.O gráfico não é ponderado.

Dos pontos acima, tenho os seguintes pensamentos:

Eu não preciso usarAlgoritmo de Dijkstra porque o gráfico não é ponderado e tentamos encontrar todos os caminhos mais curtos, não apenas um único.Eu mantenho umcount para o número de caminhos mais curtosEu gostaria de usar o BFS de v primeiro e também manter umglobal level em formaçãoEu aumento oglobal level por um de cada vez, em seguida, BFS atinge um novo nívelEu também mantenho oshortest level info para o caminho mais curto para wA primeira vez que me encontro enquanto viajo, atribuo oglobal level aoshortest level ecount++;contanto que oglobal level é igual aoshortest levelEu aumentocount cada vez que eu encontrava o w novamente.se oglobal level torna-se maior que oshortest level, Eu termino a viagem, porque estou procurando caminho mais curto não caminho.Então eu faço 2-8 novamente para w para v

Meu algoritmo está correto? Se eu fizer v para w e então w para v, isso ainda é considerado como tempo linear?