4573

Кратчайший путь в графе. Методы программирования

Курсовая

Информатика, кибернетика и программирование

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

Русский

2012-11-22

151 KB

61 чел.

1 Цели

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

2 Проектирование

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

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

Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.

Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:

  1.  Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
  2.  Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

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

В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.


Приложение А. Листинг программы

#include<iostream.h>

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define word unsigned int

int i, j, n, p, xn, xk;

int flag[11];

word c[11][11], l[11];

char s[80], path[80][11];

int min(int n)

{

int i, result;

for(i=0;i<n;i++)

 if(!(flag[i])) result=i;

for(i=0;i<n;i++)

 if((l[result]>l[i])&&(!flag[i])) result=i;

return result;

}

word minim(word x, word y)

{

if(x<y) return x;

return y;

}

void main()

{

cout<<"Vvedite kolichestvo tochek: ";

cin>>n;

 

for(i=0;i<n;i++)

 for(j=0;j<n;j++) c[i][j]=0;

for(i=0;i<n;i++)

 for(j=i+1;j<n;j++)

 {

     cout<<"Vvedite rasstoyanie ot  x"<<i+1<<" do x"<<j+1<<": ";

     cin>>c[i][j];

 }

cout<<"   ";

for(i=0;i<n;i++) cout<<"    X"<<i+1;

cout<<endl<<endl;

for(i=0;i<n;i++)

{

 printf("X%d",i+1);

 for(j=0;j<n;j++)

 { printf("%6d",c[i][j]);

  c[j][i]=c[i][j];

 }

 printf("\n\n");

}

for(i=0;i<n;i++)

 for(j=0;j<n;j++)

  if(c[i][j]==0) c[i][j]=65535; //бесконечность

cout<<"Vvedite nachalnuy tochku: ";

 cin>>xn;

cout<<"Vvedite konechnuy tochku: ";

 cin>>xk;

xk--;

xn--;

if(xn==xk)

{

 cout<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl;

 getch();

 return;}

for(i=0;i<n;i++)

 

{  flag[i]=0;

 l[i]=65535;}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa(xn+1,s,10);

 for(i=1;i<=n;i++)

 { strcpy(path[i],"X");

  strcat(path[i],s);

                     }

 do

 {  for(i=0;i<n;i++)

   if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))

   {

    if(l[i]>l[p]+c[p][i])

    {

     itoa(i+1,s,10);

     strcpy(path[i+1],path[p+1]);

     strcat(path[i+1],"-X");

     strcat(path[i+1],s);

    }

    l[i]=minim(l[i],l[p]+c[p][i]);

   }

  p=min(n);

  flag[p]=1;

 }

 while(p!=xk);

if(l[p]!=65535)

{cout<<"Put: "<<path[p+1]<<endl;

 cout<<"Dlina puti: "<<l[p]<<endl;}

else

 cout<<"takogo puti ne syshestvuet!"<<endl;

 getch();

}

Приложение B. Блок-схемы

          Блок-схема 21 – «структуры программы»

Блок-схема 2 – «Открытие файла»

Блок-схема 1 – «реализации алгоритма Дейкстры»

                          

Блок-схема 2 – «реализации алгоритма Дейкстры»

                                       

 

Блок-схема 3 – «word minim(word x, word y) – функция, которая возвращает минимальное из x и y»


 

А также другие работы, которые могут Вас заинтересовать

55314. Спостереження за вимовою парних дзвінких і глухих приголосних звуків 2.02 MB
  Мета: Вчити дітей правильно вимовляти і писати слова із дзвінкими і глухими приголосними звуками поглибити уявлення школярів про дзвінкі і глухі приголосні звуки.
55315. Все про продукти 83.5 KB
  Today we’ll speak about food. We “go shopping” for food, even “cook” something but first I want you to remember that the fourth Thursday of November is a very special day in America. On that day people all over the USA celebrate Thanksgiving Day. Let’s solve a crossword and remember the main points of its existence...
55316. Формування мовно-літературної грамотності учнів 228 KB
  Основні завдання: Зміцнення статусу української мови як державної; Створення достатньої організаційної кадрової науковометодичної матеріальнотехнічної бази для забезпечення оптимальної ефективності процесу вивчення української мови та літератури з метою...
55317. Перші князі Київської держави 27 KB
  Назвіть імена київських князів про яких ви вивчали у молодших класах Учні згадують імена перших київських князів учитель записує їх на дошці в порядку їх правління. Перші князі були вільні духом благородні мужні кращі люди часів Київської Русі.
55318. ПІРАМІДОЛОГІЯ 4.75 MB
  Поспілкувавшись з учнями що вони знають про піраміди чи вивчали в школі на уроках історії щось цікаве хто знає про існування сучасних пірамід де вони зустрічаються нам в оточуючому нас світі легко і ненавязливо викладач підводить учнів до плану дій і розподіл ролей.
55319. ПРОФОРИЕНТАЦИЯ В РАБОТЕ КЛАССНОГО РУКОВОДИТЕЛЯ 72.5 KB
  Цель моей работы: помочь учащимся ориентироваться в огромном мире профессий; оказывать консультационную помощь в выборе любимого дела; показать неразрывную связь между желаемой профессией и необходимым образованием...
55320. Дружба – найбільший скарб 225 KB
  Напишіть на ньому побажання та добрі слова своїм друзям. Тема: Якщо ви ввічливі Мета: навчити дітей ввічливо спілкуватися з ровесниками та дорослими; розширити і закріпити вміння вживати слова ввічливості; домагатися доброзичливої атмосфери в класі; виховувати в учнів ввічливість чемність доброзичливість; формувати манери культурної поведінки поглибити знання учнів про етикет і його важливість у житті людини. Але чи то уклін чи слова вітання чи лагідна усмішка спільним в них є те що привітання означає: Ти мені приємна...
55321. Олімпійський вогник 47 KB
  Мета проекту Ознайомити учнів із історією виникнення Олімпійського руху. Послідовність виконання проекту Етапи Завдання Діяльність учнів Діяльність педагога...
55322. Різдвяні зустрічі 62 KB
  Стало білим все село двічі Біла стежка біла річка Біла хата і смерічка двічі Біла хата білі коні Тільки носики червоні Діти зупиняються стають дугою.