коротшого шляху між двома станціями метро є дещо інший завданням. Алгоритм використовує повний перебір всіх вершин графа, що призведе до великої втрати часу та забере більший обсяг пам'яті.
Нижче слідують пункти, розглянуті в курсовій роботі.
) Оформлялися змістовна частина задачі знаходження найкоротших відстаней графа.
) Розроблялася алгоритм вирішення задачі.
) Розроблялися структури програми й алгоритми програмних модулів.
) Вирішив завдання на контрольному прикладі.
) Розроблявся і описувався граф.
) Виходячи з розробленого алгоритму, реалізувалася програма.
) Розроблялися системи тестів у вигляді чорних і білих ящиків.
Алгоритм був реалізований еа мові високого рівня С ++. Відладжувалася програма в середовищі розробки Microsoft Visual studio +2013.
Курсова робота виконана відповідно до вимог в повному обсязі.
Список літератури
1.Хохлов Д.Г. Основи технології модульного програмування.
Навчальний посібник - Казань: КДТУ (КАІ), 2003. 64 с.
.Павловская Т.А. С/С ++ Програмування на мові високого рівня. Изд-во Пітер, 2003. - 461 с.
3.Беліцкій Я. Енциклопедія мови Сі. М .: Світ, 1992.
.Ліпскій В. Комбінаторика для програмістів. М .: Світ, 1988.
5.Левітін А.В. Алгоритми: ввденія в розробку й аналіз./А. В. Левітін; пров. з англ. під заг. ред. С.Г. Тригуб.- М.: Видавничий дім «Вільямс», 2006. - 576 с.
6.Макконелл Дж. Основи сучасних алгоритмів/Дж. Макконелл; пров. з англ. під заг. ред. С.К. Ландо.- М.: Видавництво ЗАТ РІЦ «Техносфера», 2004. - 368 с.
7.Ананій В. Левітін Глава 8. Динамічне програмування:
Алгоритм Флойда пошуку найкоротших шляхів між усіма парами вершин//Глава 9. Жадібні методи: Алгоритм Дейкстри//Алгоритми: введення в розробку й аналіз=Introduction to The Design and Analysis of Aigorithms.- М .: Вільямс, 2006. - С. 189-195, С. 349 - 353.
.Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Ривест,
Кліффорд Штайн Алгоритми: побудова й аналіз=Introduction to Algorithms.- 2-е вид.- М .: Вільямс, 2006. - С. 1296.
.https: //ru.wikipedia
Додаток
Лістинг програми
# include stdafx.h
# include lt; iostream gt;
# include fstream
# define inf 100000//бесконечностьnamespace std;
//структура ребер
struct Edges {
int u, v,//вершини ребра
w;//вага ребра
};
const int Vmax=1000;// Максимальна кількість вершин
const int Emax=Vmax * (Vmax - 1)/2;// Максимальна количеста ребер
int i, j,//лічильники
n,//кількість вершин
e,//кількість ребер
start;// стартова вершина
Edges edge [Emax];// Створюємо змінну типу Edges
int d [Vmax];// масив в якому зберігатимуться найкоротші шляхи
bool success=false;// Для перевірки правильності введення
//алгоритм Беллмана-Фордаbellman_ford (int n, int s)
{i, j; (i=0; i lt; n; i ++) d [i]=inf; [s]=0; (i=0; i lt; n - 1; i ++) (j=0; j lt; e; j ++) (d [edge [j] .v] + edge [j] .w lt; d [edge [j] .u]) [edge [j] .u]=d [edge [j]. v] + edge [j] .w; (i=0; i lt; n; i ++) if (d [i] == inf) lt; lt; endl lt; lt; start lt; lt; - gt; lt; lt; i + 1 lt; lt; = lt; lt; Ні raquo ;; cout lt; lt; endl lt; lt; start lt; lt; - gt; lt; lt; i + 1 lt; lt; = lt; lt; d [i];
}
//Функція введення значень
bool vvod ()
{in ( input.txt ); (! in) { lt; lt; Помилка! Не вдалося відкрити файл n raquo ;;
return false;
} w; gt; gt; n; (! (in.good () amp; amp; n lt; Vmax amp; amp; n gt; 1))//перевірка правильності введення
{
cout lt; lt; Помилка (1) читання з файлу! n raquo ;;
return false;
}
cout lt; lt; Кількість вершин: lt; lt; n lt; lt; endl;
e=0;
for (i=0; i lt; n; i ++) (j=0; j lt; n; j ++)
{
in gt; gt; w;
if (! (in.good () amp; amp; w lt; inf amp; amp; w gt; -inf))//перевірка правильності введення
{
cout lt; lt; Помилка (2) читання з файлу! n raquo ;;
return false;
} (w!=0)
{[e] .v=i; [e] .u=j; [e] .w=w; ++;
