Algorytm znaleźć szereg odrębnych ścieżek w reżyserii wykresie

Question

Powiel możliwe:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

mam graf skierowany, co algorytm można użyć, aby znaleźć liczbę odrębne acykliczne ścieżki między dwoma poszczególnymi wierzchołkami i policzyć maksymalne czasy, w których dana ścieżka jest wykorzystywana w tych odrębnych ścieżkach? Dwie ścieżki są różne, jeśli odwiedzają inną liczbę wierzchołków lub odwiedzają wierzchołki w innej kolejności.

Answer 1

Jeśli stosujesz nieco zmodyfikowany algorytm Dijkstry, możesz mieć rozwiązanie z wszystkimi parami.

Wyjaśnienie: Ścieżki od u do v jest sumą następujących elementów:

1. Ścieżki z u do v który nie przechodzi przez w
2. Ścieżki, które przechodzą przez w = liczba ścieżek od u do wrazy liczba ścieżek od w do v

Inicjuj macierz za pomocą zer, z wyjątkiem sytuacji, gdy istnieje krawędź od i do j (co oznacza 1). Wtedy następujący algorytm daje wynik (all-para-path-count)

for i = 1 to n: 
    for j = 1 to n: 
     for k = 1 to n: 
      paths[i][i] += paths[i][k] * paths[k][j] 

trzeba powiedzieć: O(n^3)

Marzą ci się czytać jedno rozwiązanie pary. :)