Смекни!
smekni.com
Информатика и программирование

Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог

Информационная карта

5013Информационная 5418 Исходящий 7992 Инвентарный 5436 Инвентарный

картаАИП номер,дата номерФАП номерВНТИЦ


ИКАП———— —————————————— ——————————————— ———————————————

| 50 | | | | | | |

———— —————————————— ——————————————— ———————————————

7839Тип ЭВМ 7902 Типи версия ОС 5715 Инструмен- 7848 Оперативная

тальноеПО память

——————————— —————————————————— ——————————————— ——————————————

| | | | | | | |

——————————— —————————————————— ——————————————— ——————————————

7965РазновидностьПС 73 Библиотекапрограмм 5679Код программыпо

46Программныймодуль 82 Программнаясистема ЕСПД

55Программа 91 Программныйкомплекс ————————————————

64 Пакетпрограмм 28Информационнаяструктура | |

19Комплект программ 37 Прочее | |

————————————————

7884Объем программы————————————— 7362 Срок окончания ———————————————

| | разработки | |

————————————— ———————————————

7947Описание программы ————————— 4956 Распространение 4511 Сертифика-

| | ПП ция

7956Описаниеприменения|—————————| 35 Организация- 34 Сертифициро-

| | разработчик вана

|—————————|

7974РТО | | 44 Организация, 43 Несертифици-

————————— ведущаяФАП рована


Сведенияоб организации,представляющейАИП во ВНТИЦ


2457Код ОКПО 2934 Телефон 2394 Телефакс 2754 Город

—————————————— —————————————— ————————————— ———————————————————

—————————————— —————————————— ————————————— ———————————————————

1332Сокращенноенаименованиеминистерства(ведомства) 2403 Код ВНТИЦ

————————————————————————————————————————————————————— ———————————————

————————————————————————————————————————————————————— ———————————————

2151Полное наименованиеорганизации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

2358Сокращенноенаименованиеорганизации —————————————————————————————

—————————————————————————————

2655Адрес организации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

Сведенияоб организации-разработчике


2988Телефон 3087 Телефакс 2781 Город

—————————————— ————————————— ————————————————————————————————————

—————————————— ————————————— ————————————————————————————————————

2187Наименованиеорганизации

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

2385Сокращенноенаименованиеорганизации —————————————————————————————

| |

—————————————————————————————

2682Адрес организации

———————————————————————————————————————————————————————————————————————

———————————————————————————————————————————————————————————————————————

6183Авторы (разработчикиПС)

———————————————————————————————————————————————————————————————————————

| |

———————————————————————————————————————————————————————————————————————

9045Наименованиепрограммы

———————————————————————————————————————————————————————————————————————

| |

| |

———————————————————————————————————————————————————————————————————————

9117Реферат

———————————————————————————————————————————————————————————————————————

| |

| |

| |

| |

| |

| |

| |

| |

| |

| —————————————————————|

| |5436 |

| | |

———————————————————————————————————————————————————————————————————————

Фамилия,инициалы Должность Уч.степень, Подпись МП

звание

———————————————————————————————————————————————————————————————————————

|Руководитель|6111 |6311 |6210 | |

|организации | | | | |

|—————————————|——————————————————————|——————————|————————————|——————————|

|Руководитель|6120 |6320 |6228 | |

|разр.(ФАП) | | | | |

———————————————————————————————————————————————————————————————————————

5634Индексы УДК 7434 Дата 7506 Входящийномер

——————————————————————————————————— ———————— ——————————————————————

——————————————————————————————————— ———————— ——————————————————————

5616Коды тематическихрубрик

———————————————————————————————————————————————————————————————————————

| . . | . | . . | . | . . | . | . . | . | . . |

———————————————————————————————————————————————————————————————————————

5643Ключевое слово

———————————————————————————————————————————————————————————————————————

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

|———————————————————————————————————————————————————————————————————————|

———————————————————————————————————————————————————————————————————————



Введение


Проникновениематематикив экономическуюнауку связанос преодолениемзначительныхтрудностей.В этом отчастибыла “повинна”математика,развивающаясяна протяжениинесколькихвеков в основномв связи с потребностямифизики и техники.Ног главныепричины лежатвсе же в природеэкономическихпроцессов, вспецификиэкономическойнауки.

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

Наиболеераспространенопониманиесистемы каксовокупностьэлементов,находящихсяво взаимодействиии образующихнекоторуюцелостность,единство. Важнымкачеством любойсистемы являетсяэмерджентность– наличие такихсвойств, которыене присущи ниодному из элементов,входящих всистему. Поэтомупри изучениисистем недостаточнопользоватьсяметодом ихрасчлененияна элементыс последующимизучением этихэлементов вотдельности.Одна из трудностейэкономическихисследований– в том, что почтине существуетэкономическихобъектов, которыеможно было бырассматриватькак отдельные(внесистемные)элементы.

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

Сложностьэкономикииногда рассматриваласькак обоснованиеневозможностиее моделирования,изучение средствамиматематики.Но такая точказрения в принципеневерна. Моделироватьможно объектлюбой природыи любой сложности.И как раз сложныеобъекты представляютсобой наибольшийинтерес длямоделирования;именно здесьмоделированиеможет датьрезультаты,которые нельзяполучить другимиспособамиисследования.

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


1. Краткоеописание моделипоставленнойзадачи


Благодарясвоему широкомуприменению,теория о нахождениикратчайшихпутей в последнеевремя интенсивноразвивается.

Нахождениекратчайшегопути - жизненнонеобходимои используетсяпрактическивезде, начинаяот нахожденияоптимальногомаршрута междудвумя объектамина местности(напр. кратчайшийпуть от домадо академии),такжеиспользуетсяв системахавтопилота,используетсядля нахожденияоптимальногомаршрута приперевозкахкоммутацииинформационногопакета Internet и мн.др.


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

Сетевые моделииспользуютсядля решенияследующихзадач:

  1. проектированиегазопровода;

  2. нахождениекратчайшегомаршрута междугородами посети дорог;

  3. определениемаксимальнойпропускнойспособностипри транспортировкинефти;

  4. составлениевременныхграфиков работ и др.


Существуюттри наиболееэффективныхалгоритманахождениякратчайшегопути:

1) алгоритмпостроенияминимальногоосновногодерева. Предполагаетсоединениевсех узлов сетис помощью путейнаименьшейдлины.

2) алгоритмДейкстры.Используетсядля нахождениякратчайшегопути междузаданным исходнымузлом и любымдругим узломсети

3) алгоритм Флойда.Используетсядля нахожденияоптимальногомаршрута междулюбыми двумяузлами сети.


Основныеопределения


Сеть состоитиз множестваулов, связанныхдугами (илиребрами). Такимобразом, сетьописываетсяпарой множеств(N,A), гдеN – множествоузлов, а A– множестворебер. Например,сеть, показаннаяна рис. 1, описываетсяслед образом.


N = {1, 2, 3, 4, 5},

A = {(1, 3), (1, 2), (2, 3), (2, 4), (2,5), (3, 4), (3, 5), (4, 5)}.



С каждым типомсети связанопределенныйтип потоков(например,транспортныйпоток нефтив нефтепроводахили автомобильныепотоки в сетидорог). В общемслучае потокив сети ограниченыпропускнойспособностьюее ребер, котораяможет быть какконечной, таки бесконечной.

Ребро называетсянаправленным,или ориентированным(и в этом случаеребро будемназывать дугой),если в одномнаправлениивозможен толькоположительныйпоток, а в противоположном– только нулевой.В ориентированнойсети все ребраориентированы.

Путем называетсяпоследовательностьразличныхребер, соединяющихдва узла, независимоот направленияот направленияпотока в каждомребре. Путьформирует цикл,если начальныйи конечный узлысовпадают.Например, нарис. 2 ребра (2, 3),(3, 4) и (4, 2) составляютцикл. Ориентированныйцикл – это цикл,в котором вседуги ориентированыв определенномнаправлении.

Связная сеть– такая сеть,у которой любыедва узла связаныпо крайней мереодним путем.На рис. 1 показанименно такойтип сети и неимеющий циклов.Остовное дерево– это дерево,содержащаявсе узлы сети.На рис. 2 показаныдерево и Остовноедерево для сетииз рис. 1.



2. Математическаяформулировказадачи, обоснование

АлгоритмФлойда

Алгоритм Флойданаходит кратчайшийпуть междулюбыми двумяузлами сети.В этом алгоритмесеть представленав виде квадратнойматрицы с nстроками и nстолбцами.Элемент (i,j) равенрасстояниюdij отузла i к узлуj, котороеимеет конечноезначение, еслисуществуетдуга (i ,j),и равен бесконечностив противномслучае.

Покажем сначалаосновную идеюметода Флойда.Пусть есть триузла i, jи k и заданырасстояниямежду ними(рис. 3). Если выполняетсянеравенствоdij+ djkik,то целесообразнозаменить путьi → k путемi → j →k. Такаязамена (далееее будем условноназывать треугольнымоператором)выполняетсясистематическив процессевыполненияалгоритмаФлойда.



Алгоритм Флойдатребует выполненияследующихдействий.

Шаг 0. Определяемначальнуюматрицу расстоянийD0 и матрицупоследовательности

узлов S0.Диагональныеэлементы обеихматриц помечаютсязнаком “ – “,

показывающим,что эти элементыв вычисленияхне участвуют.Полагаем k=1.


Основной шаг.Задаем строкуk и столбецk как ведущуюстроку и ведущийстолбец.

Рассматриваемвозможностьприменениятреугольногооператора ковсем элементамdijматрицы Dk-1.Если выполняетсянеравенство


dij+ djkik(i ≠k, j≠k,i ≠j),


тогда выполняемследующиедействия :

  1. создаем матрицуDkпутем заменыв матрице Dk-1элемента dijна сумму dij+ djk,(рис. 4)

  2. создаем матрицуSkпутем заменыв матрице Sk-1элемента sijна k. Полагаемk=k+1 иповторяют шагk. (рис. 5)

–

d12

 …

d1j

 …

d1n

d21

 – …

d2i

 …

d2n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

di1

di2

 …

dij

 …

din

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

dn1

dn2

 …

dnj

 … –


рис.4




– 2 … j … n
1 – … j … n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
1 2 … j … n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
1 2 …

j

 … –


рис.5



После реализацииn шаговалгоритмаопределениепо матрицамDnи Snкратчайшегопути междуузлами iи j выполняетсяпо следующимправилам .

  1. Расстояниемежду узламиi и jравно элементуdij вматрице Dn.

  2. Промежуточныеузлы пути отузла i доузла j определяемпо матрице Sn.Пусть sij= k, тогдаимеем путь i→ j → k.Если далее sik= k и ski= j, тогдасчитаем, чтовесь путь определен,так как найденывсе промежуточныеузлы. В противномслучае повторяемописаннуюпроцедуру дляпутей от узлаi к узлу kи от узла kк узлу j.


3. Численноерешение показательногопримера


Найдем длясети, показаннойна рисунке 5,кратчайшиепути междулюбыми двумяузлами. Расстояниямежду узламиэтой сети проставленына рисункевозле соответствующихребер. Ребро(3,5) ориентировано,поэтому недопускаетсядвижение отузла 5 к узлу3. Все остальныеребра допускаютдвижение в обестороны.




Шаг 0. Начальноерешение матрицыD0 и S0строятсянепосредственнопо заданнойсхеме

сети. МатрицаD0 симметрична,за исключениемпары элементовd35 и d53,где d35 = ∞(посколькуневозможенпереход от узла5 к узлу 3).


рис. 8


S0

1

2

3

4

5

1

 – 2 3 4 5

2

 1 – 3 4 5

3

 1 2 – 4 5

4

 1 2 3 – 5

5

 1 2 3 4 –


Шаг 1. В матрицеD0 выделеныведущие строкаи столбец (k=1)(рис. 8). После этогокаждый элементпроверяетсяс помощьютреугольногооператора.Таким образом,чтобы на основематриц D0и S0 получитьматрицы D1и S1, выполняемследующиедействия:

  1. проверяем d32> d31 + d12= 20 > 30 + 100 = 20 > 130 еслиусловие принимаетистину, тоустанавливаемS32 = 1 ,а еслинет тогда всетак и остается.

Матрицы D1и S1 имеютследующий вид(см. рис. 9):

рис. 9


S1

1

2

3

4

5

1

 – 2 3 4 5

2

 1 – 3 4 5

3

 1 2 – 4 5

4

 1 2 3 – 5

5

 1 2 3 4 –


Шаг 2. Полагаемk=2. Треугольныйоператор применяетсяк элементамматриц D1и S1,

выделеннымдвойной рамкой.В результатеполучаем матрицыD2 и S2(см. рис.10):

рис. 10


S2

1

2

3

4

5

1

 – 2 3 2 5

2

 1 – 3 4 5

3

 1 2 – 4 5

4

 2 2 3 – 5

5

 1 2 3 4 –


Шаг 3. Полагаемk=3. В матрицеD2 и S2выделены ведущиестрока и столбец.

Треугольныйоператор применяетсяк элементамматриц D2и S2, выделенныедвойной рамкой.В результатеполучаем матрицыD3 и S3(см.рис.11):

рис. 11


S3

1

2

3

4

5

1

 – 3 3 3 5

2

 3 – 3 4 5

3

 1 2 – 4 5

4

 3 2 3 – 5

5

 3 3 3 4 –


Шаг 4. Полагаем k=4.Выделены ведущиестрока и столбецв матрице D3и S3.

Получаем новыематрицы (см.рис.12):

рис. 12


S4

1

2

3

4

5

1

 – 3 3 3 4

2

 3 – 3 4 4

3

 1 2 – 4 4

4

 3 2 3 – 5

5

 3 4 3 4 –


Шаг 5. Полагаем k=4.Ведущие строкаи столбец вматрице D4и S4 выделены.Никаких

действий наэтом этапе невыполняем;вычислениязакончены.

Конечные матрицыD4 и S4содержат всюинформацию,необходимуюдля определениякратчайшихпутей междулюбыми двумяузлами сети.

Для нахождениясоответствующихмаршрутовнапомним, чтосегмент маршрута(i,j) состоитиз ребра (i,j)только в томслучае, когдаsij=j.В противномслучае узлыi и jсвязаны, покрайней мере,через одинпромежуточныйузел.


4. Описаниеалгоритмаавтоматизированныхрасчетов


  1. Cоставляетсяначальнаяматрица расстоянийD0 и матрицапоследовательностиузлов S0.В каждой ячейкематрицы Dпишется элементdij,который определяетрасстояниемежду узломi и узломj, матрицаS заполняетсяавтоматически. Элемент, в которомi==j помечается“—“, он в вычислениине участвует.


  1. Шаг 1. Пока k

Определяемk-ую стокуи k-ый столбецкак ведущуюстроку и ведущийстолбец.

а) осуществляетсяпереборка всехэлементов, если dik+dkjij,то элемент dijзаменяетсяна сумму dij+dkj.При условии,что i≠k,j≠k иj≠i.

б) cоставляетсяматрица расстоянийD1 в соответствии с заменами нашаге 1 и матрицапоследовательностиузлов, в которомэлементы sijсоответствующиеэлементам dijзаменяетсяна k.

  1. Полагается,что k=k+1и повторяетсяшаг 2.


5. Расчетэкономическойэффективностирасчетноймодели


Решение задачисетевогомоделированияпри помощипрограммыкурсовой работыпо теме “Нахождениекратчайшегомаршрута междудвумя городамипо существующейсети дорог”рассчитываетминимальноерасстояниемежду любымидвумя пунктамис большой точностью,что не происходитпри решениетаких задачвручную. Результат,получаемыйпри решенииданной задачиотличаетсяот ручногорешения тем,что человекугораздо удобнееиспользоватьресурсы компьютера,а не заниматьсярутинной работой,решая однотипныезадачи вручную,что может привестик ошибочнымрезультатам.


Примернекорректныхданных с точкизрения данноймодели


Некорректнымиданными с точкизрения выбранноймодели являютсяданные, которыене удовлетворяютусловиям ограниченияданной модели.Например: привводе отрицательногорасстояниямежду городамито системавыдаст сообщение«Расстояниемежду городамине может бытьотрицательным»


Математическийанализ найденногорешения


Математическийанализ решениязадач из темы“Нахождениекратчайшегомаршрута междудвумя городамипо существующейсети дорог”показывает.Что если привводе входныхданных не былодопущено ошибки,т. е. входныеданные удовлетворяютустановленнымдля системыограничениям,то полученноерешение действительнобудет соответствоватьпоставленнойзадаче.


Экономическийанализ полученногорешения


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


6. Постановказадачи напрограммирование

Ограничениямодели


Данный проектимеет следующиеограничения:

  1. Количествовершин должнобыть в диапазоне(i=3;i

  2. расстояниямежду одними тем же узломбыть не может;

  3. Если междувершинами нетрасстояния- вводится любоеотрицательноечисло.

  4. Расстояниене может бытьравно 0.


Техническоезадание

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


Заданиена проектирование

Результатамипроектированияявляются:

  1. Рассмотрениерезультатованализа и проверкаих полноты.

Достоверныйответ на поставленнуюзадачу - этоматрица действительныхчисел, определяющаярасстояниемежду любымидвумя узламисети.

  1. Определениекритическихучастков проектаи оценка ограниченийпроекта.

Данный проектимеет следующиеограничения:

а) число узловограничено(от 3 до 50);

б) Если междувершинами нетрасстояния- вводится любоеотрицательноечисло;

в) расстояниямежду одними тем же узломбыть не может;

г) Расстояниене может бытьравно 0;

  1. Определениеархитектурысистемы.

Windows 98, Turbo C++ IDE.

  1. Принятие решенийоб использованиипродуктовдругих разработчиков,о способахинтеграциии механизмовобмена информациейс другимипрограммами.

Продукт неимеет механизмовобмена информациейс другимипрограммами.


Программа можетиспользоватьсяи копироватьсялюбым пользователемв системе Windows.

  1. Проектированиепроцесса икода: выборсредств разработки,определениеинтерфейсовпрограмм,отображениефункций системына ее модулеи определениеспецификациимодулей.

Программавыполняетнахождениикратчайшегопути междудвумя заданнымиточками методомФлойда.

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

Задача разбитана подзадачи(программа намодули):

1-ая часть – вводначальныхрасстояний.

2-ой частью являетсяопределениеведущей строкии ведущегостолбца.

3-ей – возможностиприменениятреугольногооператора ипроизведениенужной заменыв двух матрицах(расстоянийи последовательностиузлов).

2-ая и 3-я частьвыполняютсятакое числораз, сколькоузлов сети.

4-ая часть выводитрезультат наэкран.

При программированиимодулей словесныйалгоритм переводитьсяв соответствующиеоператоры ЯП.2-ой и 3-ий модуливыполняютсяв цикле.

  1. Определениетребованийк процессутестирования.

Тестирование(Testing) – этоэтап разработкипрограммы, впроцессе которогопроверяетсяработоспособностьпрограммы, несодержащейявных ошибок

Т

естированиепроизводитьсяс помощью тестов,совокупностьювходных данных,а также точногоописания вехрезультатов,которые должнавыработатьпрограмма наэтих данных.Тесты могутбыть взяты изразличныхисточниковили разработанысамим программистом.

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

  1. Определениетребованийбезопасностисистемы.

Данный продуктне связан сдругими программами,кроме егозапускаемогокода (файла *.exe)


Обоснованиевыбора языкапрограммирования

Язык Си (разработалДеннисом Ритчив 1972 г.) соединяетсвойства языкавысокого уровняс возможностямиэффективногоиспользованияресурсов компьютера,которые обычнодостигаютсятолько припрограммированиина языке Ассемблера.

Си не оченьпрост в изучениии требуеттщательностив программировании,но позволяетсоздаватьсложные и весьмаэффективныепрограммы.Потому я и выбралв качествеязыка программированияСи.


7. Руководствопользователю

Данная программанаходит кратчайшеерасстояниемежду городамипо существующейсети дорог. Призапуске программаспрашивает,какое количествовершин сети(от 3 до 50) .Послечего последовательновводится расстояниемежду вершинами(если междувершинами нетрасстояния,то ставитьсялюбое отрицательноечисло).

После вводаданных на экранвыводитьсяматрица расстоянийи матрицапоследовательностиузлов.



Если в матрицепоследовательностиузлов sij≠ j, то городаi и jсвязаны, по крайней

мере, черезодин промежуточныйузел. Рассмотримэтот случайна примере (см.«Численноерешение показательногопримера»):

Поскольку s15= 4 и s45 = 5, сначалакратчайшиймаршрут междуузлами 1 и 5 будетиметь вид 1→4→5.Но, т. к. s14≠ 4, узлы 1 и 4 в определяемомпути не связаныодним ребром(но в исходнойсети они должныбыть связанынепосредственно).Далее следует

определитьпромежуточныйузел (узлы) междупервым и четвертымузлами. Имеемs14=2 и s24=4,поэтому маршрут1→4 заменяем на1→2→4. Посколькуs12=2 и s24=4,других промежуточныхузлов нет. Комбинируяопределенныесегменты маршрута,окончательнополучаем следующийкратчайшийпуть от узла1 к узлу 5: 1→2→4→5.Длина этогопути равна 12милям.


Заключение


Данная курсоваяработа включаетв себя два предмета:«Основы алгоритмизациии программирования»и «Математическиеметоды».

В курсовойработе былирассмотреныследующиевопросы:

Данная программабыла протестированана многих примерахи на разных ПКи при этом выдавалаправильныерезультат.


Списокиспользованнойлитературы


  1. «Введение висследованиеопераций»Х.А.Таха;

  2. «Математикадля экономическихспециальностей»М.С.Красс;

  3. «Основы математикии ее приложениев экономическомобразовании»М.С. Красс, Б.П.Чупрынов;

  4. «Экономико-математическиетребования»В.А.Абчук.

  5. «C/C++ взадачах и примерах»Н.Культин.

  6. «Turbo Pascalв задачах ипримерах»Н.Культин.

  7. «Информатика»Л.З.Шауцукова.

  8. «Дискретнаяматематикадля программистов»Ф.А.Новиков.

  9. «Основы алгоритмизациии программирования»О.Л.Гальцына,И.И.Попов.

  10. «C++ Builder6 справочноепособие»А.Я.Архангельский.

  11. «Теория графов»О.И.Леонов.

  12. ссылка на алгоритмФлойдаhttp://algolist.manual.ru/maths/graphs/shortpath/floyd.php

  13. ссылка “теорияграфа”http://www.csu.ac.ru/~yan/mvs2002/Mvslab_7.htm

  14. ссылка наматематическиеграфыhttp://www.sura.ru/maxwell/scripts/math-graphs.php

  15. ссылка “вопросыо графах”http://shade.msu.ru/~mab/summer2002/test/graph.html

  16. ссылка алгоритмына Basichttp://www.rsdn.ru/res/book/prog/basic_algorithms.xml

  17. ссылкаhttp://olympiads.ru/sis/2003/plans/exam_c.doc

  18. ссылка на всеалгоритмыhttp://alglib.dore.ru/all.html

  19. ссылка “теориюграфов“http://pco.iis.nsk.su/~dyatlov/alg/graph/index.php

  20. ссылка на различныеалгоритмыhttp://www.citforum.ru/book/algoritm/algoritm_c.shtml

  21. ссылка “дискретнаяматематика”http://ermak.cs.nstu.ru/site/students/rta/control.phtm


Приложение

Описаниеалгоритма ввиде блок-схемы





Листингпрограммы

#include

#include

#define MAX_VERT 50


int main ( void )


{

clrscr ( );

intk=0,

i = 0,

j = 0,

n = 0;

intD [ MAX_VERT ][MAX_VERT ];

intS [ MAX_VERT ][MAX_VERT ];


/*-------->8-------------start>>Vvod*dannix----------------->8--------------*/


while ( n MAX_VERT ){

printf ( "\nvveditekol_vo versin v seti [ 2 >> %d ] : ", MAX_VERT );

scanf ( "%i",&n );

if ( n > MAX_VERT ||n

printf ("\nkol_vo versin dolzno bit v diapozone ot [ 2 >> %d ] !\n", MAX_VERT );

};

printf ( "\n");

for ( i=0;i

for ( j=0;j

if ( i = = j )D[i][j] = 0;

else { printf ( "A[ %i , %i ] = ", i+1, j+1 );

scanf ( "%i",&D[i][j] );

};

};

};


for ( i=0;i

for ( j=0;j

if ( i==j ) S[i][j] =0;

else S[i][j] = j+1;

};

};


/*-------->8---------------end>>Vvod*dannix----------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>resenia*dannix-------------->8---------------*/


for( k=0;k

for( i=0;i

if ( k==i ) continue;

for ( j=0;j

if ( k = = j || i = =j ) continue;

if ( ( ( D[i][j] >( D[i][k] + D[k][j] ) )

|| D[i][j] 0

&& D[i][k] >0 ){

D[i][j] = ( D[k][j]+ D[i][k] );

S[i][j] = k+1;

};

};

};

};


/*-------->8---------------end>>resenia*dannix-------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>vivoda*dannix--------------->8---------------*/


printf ( "\n\t");

printf ( "MatrixaRastoqnij :" );

printf ( "\n\n");

for ( i=0;i

for ( j=0;j

printf ( "%5i",D[i][j] );

};

printf ( "\n");

};

printf ( "\n\t");

printf ( "MatrixaPosledovatelnosti yzlov :" );

printf ( "\n\n");

for ( i=0;i

for ( j=0;j

printf ( "%5i",S[i][j] );

};

printf ( "\n");

};


/*-------->8---------------end>>vivoda*dannix--------------->8--------------*/


printf( "\n ");

getch();

return0;

};

принял


…………………………………….

 Лист
Н.контр.


23

Утв.

Лист




МинистерствообразованияРоссийскойФедерации

Департаментобразованияи науки Краснодарскогокрая

Колледж «………………………..»


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


по предмету:«Математическиеметоды»

на тему:«Нахождениекратчайшегомаршрута междудвумя городамипо существующейсети дорог»


Выполнил:

Студент

Группы……….. …………..


шифр:2203021


Руководитель …………………...


Дата


г. Краснодар

2004



СОДЕРЖАНИЕ








……………………………..






Изм Лист № документа Подпись Дата Разраб. ……………..

Нахождениекратчайшегомаршрута междудвумя городамипо существующейсети дорог Лит. Лист Листов Пров. ……………..






Т.контр





Н. контр.


Утв


 
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.