Numero di percorsi più brevi in ​​un grafico

Question

Devo trovare il numero di tutti i percorsi tra due nodi di un grafico utilizzando BFS. Penso che la risposta alla mia domanda può essere trovato qui:

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

Ma io non capisco esso. Qualcuno potrebbe scrivere l'algoritmo in altre parole in modo da poterlo capire meglio?

Answer 1

Diciamo che è necessario passare da src a dest.

Con ogni vertice x associate due valori count e val, count è il numero del percorso più breve da src a x e val è la distanza più breve da src a x. Mantenere anche una variabile visitata che dice se il nodo è arrivato prima volta di no.

Applicare solito algoritmo BFS,

Initialize u = src 
visited[u] = 1,val[u] = count[u] = 1 
For each child v of u, 
    if v is not visited 

Un nodo viene visitato prima volta quindi ha un solo percorso dalla sorgente ad oggi tramite u, quindi più breve percorso fino v è 1 + percorso più breve fino u, e il numero di modi per raggiungere v tramite il percorso più breve è uguale a contare [u] perché dici che hai 5 modi per raggiungere dalla fonte, quindi solo questi 5 modi possono essere estesi fino a v poiché v si incontra per la prima volta via u, quindi

val[v] = val[u]+1,  
count[v] = count[u], 
visited[v] = 1 

if v is visited 

Se v è già visitato, il che significa che esiste un altro percorso fino a v tramite un'altra v ertices, poi tre casi si pone:

1 :if val[v] == val[u]+1 

se val corrente [v] che è dist fino v attraverso qualche altro percorso è uguale a val [u] +1, cioè abbiamo distanze più brevi uguali per raggiungere v impiego di corrente percorso attraverso u e l'altro percorso fino a v, quindi la distanza più breve fino a v rimane la stessa, ma il numero di percorso aumenta per il numero di percorsi di raggiungere u.

count[v] = count[v]+count[u] 

2: val[v] > val[u]+1 

Se percorso di corrente di raggiungere v è inferiore al valore precedente di val [v], quindi val [v] viene memorizzato percorso di corrente e conteggio [v] viene aggiornato

val[v] = val[u]+1 
count[v] = count[u] 

Il terzo caso è se il percorso corrente ha distanza maggiore del percorso precedente, in questo caso, non è necessario modificare i valori di val [v] e contare [v]

Eseguire questo algoritmo fino al completamento del BFS. Alla fine val [dest] contiene la distanza più breve dalla sorgente e il conteggio [dest] contiene il numero di vie da src a dest.