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»


 

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

59545. Обязанности проводника при приемке и подготовке вагонов в рейс. Сооружения и устройства вагонного хозяйства 80.5 KB
  Назвіть кольори веселки. Що в неживій природі нагадує ці кольори Сонце світло вогонь ліхтар. Тепер розглянемо останні три кольори: блакитний синій фіолетовий. Де в неживій природі можемо побачити ці кольори Небо вода сніг лід.
59547. Боротьба ОУН „УПА” У 40-х – на початку 50-х років 66.5 KB
  Основні поняття: ОУН організація українських націоналістів український політичний рух що ставив собі за мету встановлення незалежної української держави. Отже наша тема: Боротьба ОУН УПА у 40х на початку 50х років. Що таке депортація розвитку безкоштовної освіти...
59550. Велика буква у назвах міст, сіл, вулиць та річок 48.5 KB
  Загарбники люди розповідали що після звільнення міста спорудили на його підступах багато камяних левів. Летимо далі і наступна посадка буде в місті Харкові. Хто розповість нам легенду звідки пішла назва міста Був собі козак Харко.
59551. Сценарій літературно-музичного свята. Від сопілки — до слова, від слова — до мови 51 KB
  Перший ведучий. Із святом рідної мови вас, шановні добродії, із святом, шанувальники рідного слова. Мова — то цілюще джерело, і хто не припаде до нього вустами, той сам усихає від спраги.
59552. Разработка сетевого формата конкурентоспособного бизнеса по управлению коттеджной недвижимостью в интересах его широкого выведения на рынок 1.44 MB
  Проблема исследования относится к стратегическому менеджменту и может быть сформулирована как неопределенность, связанная с предложением такого формата услуг по управлению коттеджной недвижимостью, который позволил бы сформировать конкурентоспособный бизнес в целях его широкого выведения на рынок этих услуг при сопоставимых издержках.
59553. Бінарний урок. Весна в житті тварин 42 KB
  Обладнання: ілюстрації тварин предметні малюнки індивідуальні картки карта Великобританії аудіозапис пісень. Сьогодні на уроці діти ми поговоримо про особливості життя тваринного світу весною. Актуалізація знань Зараз ми відгадаємо загадки про тварин...