Я ищу эффективный способ прохождения большого графа со многими исходными вершинами и множеством вершин назначения. В частности, я хотел бы найти кратчайший путь для каждой пары (источник, место назначения), если такой путь существует. Очевидно, что это можно сделать с помощью поиска в ширину для каждой отдельной исходной точки, но, учитывая, что многие пути в графе будут пересекаться несколько раз, я думаю, что будет более короткий путь.
Следующие фактыможет иметь отношение:
- График направлен и очень разрежен. Он имеет несколько циклов.
- Для подавляющего большинства пар (источник, место назначения) путь не существует.
- Мой граф реализован на C ++ как узлы с указателями на родителей и детей (возможен двунаправленный обход). К краям прикреплены веса.