Поиск кратчайшего пути в графе - реферат по программному обеспечению, программированию

 

Тезисы:

  • В данной работе была изучена тема "Поиск кратчайшего пути в графе" на основе алгоритма Дейкстры.
  • Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
  • Известны кратчайшие пути, ведущие из исходной вершины к помеченным.
  • Массив path [i] . В нем будет хранится шаг кратчайшего пути между i и х1.
  • Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути.
  • Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение) .
  • Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.
  • В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа.
  • Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
  • Выберем из этих путей кратчайший.
Читать онлайнСкачать реферат

 

 

Похожие работы:

Еще похожие работы

Предметы

Все предметы »

 

 

Актуальные рефераты по программному обеспечению, программированию