4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

48 чел.

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»


 

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

59326. Сценарій новорічного свята 51.5 KB
  Добрий вечір вам малята любі хлопці тай дівчата. добрий вечір шановне панство В. Добрий вечір пані та панове О. Як ви хочете щоб ми провели сьогоднішній вечір урочисто Чи так щоб всім сподобалось...
59327. Сценарій фестивалю “Повір у себе” 32.5 KB
  Весна. Цвіте на землі і летить у небесах, як сонячна богиня волі, розбуджує природу, звільняє від снігів і морозів землю, розсіває квіти і квітчає сади. Весна – це поклик молодості, голос радості й щастя, віри й любові, надії й краси, поезії й пісні.
59328. Ток-шоу “Дзеркало” 53.5 KB
  В його програмі будуть висвітлюватися актуальні питання опираючись на твори мистецтва та досвід з власного життя. Яке ще призвання Туди ідуть щоб забезпечити собі безбідне і спокійне життя.
59329. Місце Т. Шевченка в українському національному відродженні 42.5 KB
  Тарас Оксано Подивись що я намалював. Оксана Ой як гарно яка хатинка Тарас а ти мене колинебудь намалюєш Тарас Звичайно. А вірша про тебе складу хочеш Голос мачухи: Тарас Тарас Ой лихо мені.
59330. Повторення таблиць множення і ділення чисел 2 і 3. Складання задач на дві дії за даним виразом. Знаходження значень буквенних виразів 39 KB
  Мета: Виявити обсяг і якість знань про множенні і ділення таблиць 2 і 3, рівень навичок у лічбі та обчислювальній діяльності; Вдосконалити вміння учнів розв’язувати задачі на 2 дії за даним виразом. Розвивати пам’ять, логічне мислення, зв’язне мовлення, увагу.
59332. Мамо, тобі низенько вклонюсь 36.5 KB
  Син: Чому у тебе у косі ясна Забриніла раптом сивина Мати: Од любові од. Син: А в бабусі голова біліш То ж мене бабуся любить більш Мати: В неї діти доньки і сини Додають сердешній сивини. Син: Чом же тітка біла як зима В неї ж діток не було й нема Мати: Так синочку біла геть вона...
59334. Відкритий урок „Тарас Шевченко” 43 KB
  Портрет Тараса Шевченка рушники серветки. Тарасова доля то правда жива. Тарасе наш Кобзарю всюди Приходиш нині ти як свій Тебе вітають щиро люди На всій Україні моїй.