4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

49 чел.

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»


 

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

44589. Передача данных по сети 53.5 KB
  Пример передачи данных 1 Компьютер-отправитель устанавливает соединение с принтсервером. Если бы использовался более сложный протокол и соответствующие ему сетевые службы то время передачи увеличилось бы но зато повысилась бы достоверность передачи. Указанный в пакете адрес отправителя в этом случае использовался бы сетевой службой для формирования подтверждения и передачи его соответствующему приемнику.
44590. Стандарт 10BaseT 39.5 KB
  ЛВС стандарта 10BseT может обслуживать до 1024 компьютеров. Сеть стандарта 10BseT Достоинством является возможность использования распределительных стоек и панелей коммутации что позволяет легко перекоммутировать сеть или добавить новый узел без остановки работы сети.
44591. Стандарт 10Base2 59 KB
  С использованием репитеров может быть увеличена общая протяженность сети введением дополнительных сегментов. Два из пяти сегментов являются межрепитерными связями и служат только для увеличения длины сети . Максимальное число компьютеров до 1024 а общая длина сети до 925м.
44592. Стандарт 10Base5 38.5 KB
  Главный кабель к которому подключаются трансиверы для связи с РС имеет длину до 500 м и возможность подключения до 100 компьютеров. С использованием репитеров которые также подключаются к магистральному сегменту через трансиверы общая длина сети может составить 2500 м.
44593. Стандарт 10BaseFL 43 KB
  Сеть стандарта 10BseFL Особенность этих трансиверов в том что их передатчики преобразуют электрические сигналы от ЭВМ в световые импульсы а приемники световые в электрические. Популярность использования 10BseFL обусловлена: высокой помехозащищенностью; возможностью прокладки кабеля между репитерами на большие расстояния т.
44594. Стандарт 100BaseX Ethernet 40.5 KB
  Его особенностью является то что он сохранил стандартный для Ethernet метод доступа CSM CD от которого отходили разработчики других технологий повышенной скорости передачи в сети. Сохранение метода доступа означает что имеющиеся в наличие драйверы для Ethernet будут работать без изменений. Преимуществом этой технологии появившейся в конце 1993 года является то что степень ее совместимости с Ethernetсетями позволяет интегрировать ее в эти сети с помощью двухскоростных сетевых адаптеров или мостов.
44596. Сетевые архитектуры ArcNet и ArcNet Plus 48 KB
  Физическая топология звезда шина звезда шина; логическая топология упорядоченное кольцо; широкополосная передача данных 25 Мбит с и 20 Мбит с для rcNet Plus; метод доступа маркерный; средой передачи может быть: коаксиальный кабель длиной 600 м при звезде и 300 м при шине; витая пара максимальная длина 244 м при звезде и шине; Компьютеры могут быть коаксиальным кабелем связаны в шину или в иных случаях подключены к концентраторам которые могут быть: пассивными; активными; интеллектуальными....
44597. Token Ring (Маркерное кольцо) 61.5 KB
  Физическая топология звезда; логическая топология кольцо; узкополосный тип передачи; скорость передачи 4 и 16 Мбит с; соединение неэкранированной и экранированной витой пары; метод доступа маркерное кольцо. Формат кадра используемый в сетях Token Ring Аппаратные компоненты Логическое кольцо в этой сетевой архитектуре организуется концентратором который называется модулем множественного доступа MSU MultySttion ccess Unit или интеллектуальным модулем множественного доступа SMU Smrt Multysttion ccess Unit....