Число кратчайших путей в графе

Ответ 1

Скажем, вам нужно перейти от src к dest.

С каждой вершиной x свяжите два значения count и val, count - это число кратчайшего пути от src до x, а val - кратчайшее расстояние от src до x. Также поддерживайте посещенную переменную, указав, прибывает ли node в первый раз.

Применить обычный алгоритм BFS,

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

A node посещается в первый раз, поэтому он имеет только один путь от источника до настоящего времени через u, поэтому самый короткий путь до v - это 1 + самый короткий путь до u, а количество способов достижения v по кратчайшему пути такое же, как и count [u], поскольку говорят, что u имеет 5 способов достичь от источника, тогда только эти 5 способов могут быть расширены до v, поскольку v встречается впервые через u, поэтому

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

if v is visited

Если v уже посещен, что означает, что путь другой путь до v через некоторые другие вершины, то возникают три случая:

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

если текущий val [v], который является dist до v через какой-либо другой путь, равен val [u] +1, т.е. мы имеем равные кратчайшие расстояния для достижения v, используя текущий путь через u, а другой путь до v, тогда кратчайшее расстояние до v остается таким же, но число пути увеличивается по числу путей достижения u.

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

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

Если текущий путь достижения v меньше предыдущего значения val [v], тогда val [v] хранит текущий путь, а счетчик [v] также обновляется

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

Третий случай: если текущий путь имеет расстояние больше предыдущего пути, в этом случае нет необходимости изменять значения val [v] и count [v]

Сделайте этот алгоритм до завершения BFS. В конце val [dest] содержит кратчайшее расстояние от источника, а count [dest] содержит количество путей от src до dest.