Алгоритмы на графах. Нахождение кратчайшего пути»

Войдя в человеческую жизнь, компьютеры стали неотъемлемой частью нашей цивилизации. Однако технологический прогресс, спровоцированный широкомасштабным развитием компьютерной техники, связан не только и не столько с увеличением производительности компьютеров и наращиванием мощностей распределенных вычислительных сетей, но в большей степени он обусловлен использованием программного обеспечения, позволяющего автоматизировать работу практически любого сотрудника на предприятии.
Программное обеспечение или компьютерные программы - это последовательность инструкций, предназначенных для исполнения устройством управления вычислительной машины. Процесс разработки программного обеспечения состоит из нескольких этапов, из которых лишь непосредственное создание программного кода носит название «программирование».
Одним из этапов написания компьютерных программ является алгоритмизация - процесс построения алгоритма решения задачи. Алгоритм – это набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Язык программирования (англ. Programming language) - система обозначений для описания алгоритмов и структур данных, определенная искусственная формальная система, средствами которой можно выражать алгоритмы.
Язык программирования освобождает программиста от необходимости решения своих задач и написания программного кода на неудобном для него языке машинных команд и предоставляет возможность использовать специальные языки более высокого уровня.
Одной из востребованных задач, компьютерное решение которой находит применение во всех сферах жизнедеятельности человечества, является нахождение кратчайшего пути.
Данная задача используется практически везде, например, нахождение оптимального маршрута между двумя объектами на местности, в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Кратчайший путь рассматривается при помощи...

Нахождение кратчайшего пути в наши дни является порой жизненно необходимой задачей и часто используется во многих сферах жизни, начиная от нахождения оптимального расстояния, например, между двумя городами, до нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, который именуется графом. Задача поиска кратчайшего пути производится между двумя заданными вершинами в графе. Результатом поиска является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.
Граф - это множество точек и попарно соединяющих их линий (не обязательно прямых). Граф схематично изображают на плоскости в виде точек (вершин) и соединяющих его линий (ребер).
В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.
Наиболее эффективными алгоритмами нахождения кратчайшего путив графе являются:
- алгоритм Дейкстры;
- алгоритм Флойда;
- переборные алгоритмы.
Наиболее простым в реализации является алгоритм голландского ученого Эдсгера Дейкстры, который находит все кратчайшие пути из одной изначально заданной вершины графа до всех остальных. С его помощью, при наличии всей необходимой информации, можно, например, узнать какую последовательность дорог лучше использовать, чтобы добраться из одного города до каждого из многих других, или в какие страны выгодней экспортировать нефть и т. п. Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом, т. е. если, например, некоторая система предусматривает убыточные для фирмы маршруты, то для работы с ней следует воспользоваться отличным от алгоритма Дейкстры методом.
Кратко суть алгоритма Дейкстры можно описать так:
- допустим, необходимо найти кратчайший путь из вершины A в вершину E.
- перебирая все возможные расстояния до вершин, находим из них...