4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

40 чел.

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»


 

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

76149. Классификация строительных материалов органические неорганические 115.5 KB
  Всемирный форум по устойчивому развитию состоявшийся в Йоханнесбурге в сентябре 2002 г. определил как одну из главных задач на XXI в. необходимость сочетания социальных экологических высокотехнологичных и экономических вопросов в решении глобальных проблем всей планеты...
76152. Специальные операции реляционной алгебры 27.82 KB
  Основная идея реляционной алгебры состоит в том что коль скоро отношения являются множествами то средства манипулирования отношениями могут базироваться на традиционных теоретикомножественных операциях дополненных некоторыми специальными операциями специфичными для баз данных.
76153. Технологии 3Dпечати 419.7 KB
  Исходным продуктом является жидкий фотополимер в который добавлен специальный реагентотвердитель и эта смесь напоминает всем известную эпоксидную смолу только в обычном состоянии она остается жидкой а полимеризуется и становится твердой под воздействием ультрафиолетового лазера.