Алгоритм Дейкстры

  • Просмотров 3408
  • Скачиваний 86
  • Размер файла 307
    Кб

1. Постановка задачи Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей: 1) Изучение конкретного раздела дискретной математики. 2) Решение 5-ти задач по изученной теме с методическим описанием. 3) Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса. 2. Введение 2.1 Теоретическая часть дискретный математика программа интерфейс Пусть дан граф

G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sX до заданной конечной вершины tX, при условии, что такой путь существует, т.е. при условии tR(s). Здесь R(s) – множество, достижимое из вершины s. Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том,

чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и xi – некоторая его вершина, то, двигаясь от s к xi, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует. Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути

(простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть из следующего факта. Если из каждого элемента cij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=[cij'], все элементы cij' которой отрицательны. Тогда кратчайший путь от s к t – с исключением отрицательных циклов – необходимо будет гамильтоновым, т.е.

проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n-1)×L, то кратчайший путь (простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице C. Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому мы будем