Jump to content


Photo

Поиск кротчайшего пути по алгоритму Дейкстры


  • Please log in to reply
2 replies to this topic

#1 JohnSmith

JohnSmith

    Newbie

  • Members
  • Pip
  • 5 posts

Posted 07 September 2016 - 07:57 AM

Добрый день. Столкнулся с проблемой при поиске кротчайшего пути между двумя элементами.

Пример кода:

IEnumerable<DataEdge> list;
DataVertex v = Area.LogicCore.Graph.Vertices.First();
DataVertex v_= Area.LogicCore.Graph.Vertices.Last();
var algo = new QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm<DataVertex, DataEdge>(Area.LogicCore.Graph, weight);
var predecessor = new QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<DataVertex, DataEdge>();
using (predecessor.Attach(algo))
  {
   algo.Compute(v);
   predecessor.TryGetPath(v_, out list);
  }

При формировании графа я создаю ребра в разных направлениях (например v -> v1 -> v2 <- v_), поэтому алгоритм Дейкстры из QuickGraph не может вернуть путь от вершины v до вершины v_.

При формировании графа с ребрами в обе стороны алгоритм Дейкстры работает, но возрастает кол-во ребер в 2 раза и граф начинает тормозить. Пробовал при создании ребра в обратную сторону делать SkipProcessing = Freeze, но на плавность и скорость работы графа это никак не повлияло.

Есть ли какие-либо пути решения создания неориентированных (или наоборот двунаправленных)  ребер, или другие подходы?



#2 Alexander Smirnov

Alexander Smirnov

    Staff Member

  • Administrators
  • 542 posts

Posted 08 September 2016 - 08:07 AM

Здравствуйте, GraphX использует базовые классы Quickgraph, а входящие в его состав алгоритмы работают на модели графа не связанной с визуализацией. Похоже, что реализация дийкстры в самом Quickgraph выбирает только выходящие ребра, игнорируя входящие, т.е. работает для направленного графа. Для решения схожей задачи мы использовали копию графа с избыточным количеством ребер, где между двумя вершинами всегда было 2 ребра в обе стороны. На этой копии производился поиск кратчайшего пути и выбирались вершины по идентификаторам, в то же время для отображения использовался отдельный граф без доп. ребер (оригинальный).

 

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

 

Так же рекомендую обратиться к русскоговорящим ребятам, которые сейчас подхватили разработку Quickgraph и дорабатывают библиотеку. 

https://github.com/Y...ctor/QuickGraph


If you have any questions about software feel free to use the forums or e-mail to support@panthernet.org

For all questions related to sales please mail to sales@panthernet.org


#3 JohnSmith

JohnSmith

    Newbie

  • Members
  • Pip
  • 5 posts

Posted 08 September 2016 - 10:24 AM

Спасибо за оперативный ответ. Попробую написать ребятам, но пока тогда буду использовать копию графа с 2 ребрами между узлами






0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users