Trovare tutti i percorsi più brevi dalla sorgente a tutti i vertici in un digrafo - algoritmo, algoritmo grafico, percorso più breve, grafico diretto

Ci viene dato un grafico diretto G (possibilmente con cicli) con pesi di bordo positivi e la distanza minima D[v] ad ogni vertice v da una fonte viene anche dato (D è una matrice in questo modo). Il problema è trovare la matrice N[v] = number di percorsi di lunghezza D[v] da s a v, in tempo lineare.

Ora questo è un problema di compiti a casa che sono statolottando per molto tempo. Stavo lavorando sul seguente pensiero: sto cercando di rimuovere i cicli scegliendo opportunamente un sottografo di G aciclico, e poi cerco di trovare i cammini più corti da s a v nel sottografo.

Ma non riesco a capire in modo esplicito cosa fare, quindi apprezzerei qualsiasi aiuto, come in un'idea qualitativa su cosa fare.

risposte:

Puoi usare programmazione dinamica avvicinarsi qui e riempire il numero di percorsi mentre si va, se D[u] + w(u,v) = D[v], qualcosa di simile a:

N = [0,...,0]
N[s] = 1 //empty path
For each vertex v, in *ascending* order of `D[v]`:
for each edge (u,v) such that D[u] < D[v]:
if D[u] + w(u,v) = D[v]: //just found new shortest paths, using (u,v)!
N[v] += N[u]

La complessità è O(VlogV + E), supponendo che il grafico non sia spartito, O(E) è dominante.

Spiegazione:

Se c'è un percorso più breve v0->v1->...->v_(k-1)->v_k a partire dal v0 a v_k, poi v0->...->v_(k-1) è un percorso più breve da v0 a v_k-1, quindi - quando itera v_k - N[v_(k-1)] era già stato calcolato completamente (ricorda, tutti i bordi hanno pesi positivi e D[V_k-1] < D[v_k]e stiamo iterando aumentando il valore di D[v]).
Quindi, il percorso v0->...->v_(k-1) è contato nel numero N[V_(k-1)] a questo punto.
Da v0->...->v_(k-1)-v_k è un percorso più breve - significa D[v_(k-1)] + w(v_k-1,v_k) = D[v_k] - quindi la condizione si manterrà, e aggiungeremo il conteggio di questo percorso a N[v_k].

Si noti che la dimostrazione di questo algoritmo sarà fondamentalmente l'induzione che seguirà le linee guida da questa spiegazione in modo più formale.