Беллман-форд можно сделать за одну итерацию?

Есть ли у каждого графа такой порядок ребер, что после выполнения одной итерации алгоритма Беллмана-Форда в соответствии с этим порядком каждая вершина помечается кратчайшим путем к источнику?

я уверен, что ответ положительный, но я не могу придумать алгоритм, способный найти порядок ребер, спасибо =]


algorithm bellman-ford graph-algorithm
person Jhonas    schedule 01.12.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Топологически отсортируйте дерево кратчайших путей.

person David Eisenstat    schedule 01.12.2014
comment
В этом есть смысл! Но лучше запускать dfs/bfs на дереве кратчайших путей (начинать с исходного кода и использовать ребра (u,v)=(parent[v],v)), я думаю, что кодировать намного проще. - person Ralor; 02.12.2014