Количество наилегчайших путей из одной исходной вершины

Вы можете сделать это довольно эффективно, если у вас также нет негативных граней.

Обозначим кратчайший путь к узлу v как D(v)

сортировать вершины по расстояниям - O(VlogV)

Обозначим P(v) - количество путей, ведущих от источника к v.
Теперь вы можете использовать DP для решения этого отношения (от первого до последнего):

P(source) = 1
P(v) = sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) }

Сложность алгоритма O(VlogV + E)

Доказательство правильности: по индукции (рекомендации):
базовое предложение для источника, существует единственный путь (пустой путь).
предположим, что P(v) верно для каждого v такого, что D(v) < D(u).

Для каждого кратчайшего пути, который заканчивается на u, он должен проходить через одну из вершин, таких что D(v) < D(u). Учитывая кратчайший путь source->...->v->u, путь считается в P(v). Кроме того, он не засчитывается ни для каких других P(v'), поэтому засчитывается ровно один раз в sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) }.
Кроме того, для любого пути, который не является кратчайшим путем, по предположению индукции он не учитывается ни для одного v, такого как D(v)<D(u), поэтому путь должен быть сгенерирован на последнем шаге, но ограничение (u,v) is an edge and D(u) + w(u,v) = D(v) препятствует этому, поэтому мы не учитываем ни один некратчайший путь.
КЭД