Описание теории графов. Алгоритм Флойда и Декстры.

• 1 слайд

  Курсовая робота:
  по курсу «Кросс-платформенное программирование».
  На тему:
  «Разработка программы для отыскания кратчайшего пути на графе».
  Выполнил: Коломиец Н.Ю.
  Руководитель: Сукиасов В.Г.
  

• 2 слайд

  Кроссплатформенное программное обеспечение-
  программное обеспечение, работающее более чем на одной аппаратной платформе и/или операционной системе.
  

• 3 слайд

  Кросс-платформа.
  
  
  
  
  Языки
  WEB
  С,С++
  Пере компилируемые
  JAVA, C#
  Интерпретируемые
  PHP,perl,Ruby
  

• 4 слайд

  Теория графов.
  

• 5 слайд

  Сравнения алгоритма Дейкстры и алгоритма Флойда.
  алгоритм Дейкстры
  Очень быстра я работа;
  Работает с дугами не отрицательного веса;
  Сложен в реализации;
  Ищет за один проход только длины из одной вершины до остальных;
  Применяется в многих маршрутизаторах:
  
  алгоритма Флойда
  Работает медленно;
  Прост в реализации;
  Работает с отрицательными весами дуг;
  Ищет за один проход сразу все длины кратчайших путей;
  

• 6 слайд

  Интерфейс программы.
  

• 7 слайд

  Спасибо за внимание.
  

Краткое описание документа:

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.