Вычисление длины самого длинного простого пути от города А до города В в заданной системе односторонних дорог

Министерство Образования Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

Курсовая работа

по практикуму на ЭВМ: «Структуры данных и алгоритмы»

Факультет:                ПМИ

Группа:                      ПМи-81

Студент:                    Дубина Н.Г.

Преподаватель:         Хиценко В.П.

Новосибирск 2009

1. Условие задачи

              Найти длину самого длинного простого пути от города А до города В в заданной системе односторонних дорог.

2. Анализ задачи

2.1. Исходные данные задачи:

namestart €  город, namestop € город, S-система дорог,

S={(name1_i , name2_i, ves_i)| name1_i , name2_i  €  город, ves_i €  R, i=1,…n},

город = {p_i|p_i €  {подмножество латинских букв}, j=1,…,20}, где name1_i  - город начала дороги name2_i  - город, конец дороги, ves_i – длина дороги;

2.2. Результат:

dist €  R .

2.3. Решение:

 Математическая модель системы односторонних дорог – это взвешенный ориентированный мультиграф G=(X, U) c весовой функцией w:U       R, причем w(u, v)>0, для любых (u, v) принадлежит  Е. Вершины – города, ребра – односторонние дороги между этими городами. Метка вершины – название города. Дуга (u, v) ведет из вершины u в вершину v причем город соответствующий началу пути – вершина u концу пути – v.  Вес дуги – длина расстояния между городами.

Формальная постановка задачи

              В ориентированном взвешенном мультиграфе найти максимальной длинны простой путь между двумя вершинами.

              Простой путь на графе – это такой маршрут в котором ни одна из вершин не повторяется.

Для поиска такого пути возможно просматривать граф в ширину начиная из вершины x₀ – вершины начала пути, помечая вершины  значениями – метками их расстояний от x₀ . Метки могут быть временные или окончательные. Временная метка x_j – это максимальный по длине путь от x₀ до  x_j, когда в определении пути на графе учитываются не все маршруты из x₀ до x_j. Окончательная метка  x_j – это максимальной длины путь на графе от x₀ до x_j. Таким образом в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные  метки. А остальные их часть – временные.  Алгоритм заканчивается, когда вершина z – вершина конца пути, получает окончательную метку, т.е. максимальный по длине путь от x₀ до z.

              Решение данной задачи состоит в поочередном рассмотрении наибольших  длин ребер, выявляя такой путь который являлся бы максимальным.

при dist(x₀)=0, метка (namestart)=1, y=x₀, ;

  повторять

       если метка = 0 и dist(x_i)>dist(namestart)+w_i,j

           dist(x_i)=  dist(namestart)+w_i,j ;

         если  x_i €  X и метка(x_i)=0 то

      dist(y)=min(dist(x_i));

 метка(y)=1;

i=i+1;

пока метка(namestop)=0;

Для решения понадобится матрица весов графа W_ij

                  Плюсы представления

1)  Достаточно быстрый поиск максимального по длине пути.

Минусы представления

2)  Расходуется большой объем оперативной памяти.

Основные задачи:

              1) Поиск максимальных по длине путей  между заданными городами в системе дорог S.

              2)Ввод системы дорог.

3. Структуры данных, используемые для представлений исходных данных и результатов задачи.

3.1. Входные данные

Внешнее представление системы односторонних дорог:

<система-дорог>::=<количество-городов><список – дорог>

<список – дорог>::=<дорога>|пробел<дорога><список – дорог>

<дорога>::=<откуда>пробел<куда>

<откуда>::=<название>

<куда>::=<название>

<название>::=<элемент>|<элемент><название>

<длинна - дороги>::=вещественное число

<количество – городов>::=натуральное число

<элемент>::=символ из подмножества латинских букв

Внешнее представление

              Для решения задачи граф представим  в виде его матрицы весов W. Где w_i,j – вес ребра, то есть длинна пути между i-ой и j-ой вершинами I,j=1,2…n.

3.2.Выходные данные

 Внешнее представление

dist –действительное число –длина путь между городами

Внутреннее представление

float dist;

4. Алгоритм решения задачи

4.1. Укрупненный алгоритм решения задачи

{ввод информации о системе дорог и формирование матрицы весов;

    namestart  = город начала пути

    namestop = город назначения

      поиск самого длинного пути;

      result  = {города через которые проходит маршрут}

      dist  = максимальная длина пути

}

4.2. Алгоритм поиска максимального пути

{

      for (x €  X){

         метка(x)=0;

         dest(x)=0;

}

    y=x₀;

     метка (x₀)=1;

    while (метка(z)=0){

  for (x принадлежит X){

              if (метка(x) и dist(x)>dist(y)+w_ij){