У меня есть большой, связанный, разреженный граф в форме списка смежности. Я хотел бы найти две вершины, которые как можно дальше друг от друга, то естьдиаметр графика и две вершины достигают этого.

Меня интересует эта проблема как в ненаправленном, так и в направленном случаях, для разных приложений. В направленном случае меня, конечно, волнует направленное расстояние (кратчайший направленный путь от одной вершины к другой).

Is there a better approach than computing all-pairs shortest paths?

EditПод «как можно дальше друг от друга» я, конечно, имею в виду «самый длинный кратчайший путь»; - то есть максимум по всем парам вершин кратчайшего расстояния от одной до другой.