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»


 

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

69357. Автоматизація оброблення інформації у податковій сфері 189 KB
  Система оподаткування це комплекс діючіх в державі законодавче затверджених видів податків і платежів та механізм їх нарахування. В даний час існують більше двох десятків загальнодержавних обовязкових податків і платежів ПДВ-акцизний збір-податок...
69358. Функціональне забезпечення автоматизованої системи Казначейства 134 KB
  Державне казначейство України (ДКУ) засновано в 1995 році для здійснення управління виконанням державного бюджету, моніторингу та контролю над оборотом державних фінансових ресурсів та активів. З часом функції Казначейства розширюються в напрямку обслуговування операцій місцевих бюджетів...
69359. Автоматизація оброблення інформації у страховій галузі 75.5 KB
  З утворенням недержавних страхових компаній (СК) з’явилась система страхування. Страхівник (Страхова компанія) виконує умови страхування і пропонує їх клієнтам. Якщо клієнтів влаштовують умови договору, то вони підписують договір і вносять по ньому страхові внески.
69360. Автоматизація внутрібанківських розрахункових 105 KB
  Обслуговування клієнтів банку організовується у відповідності з його організаційною структурою. Депозитний відділ. Його основною задачею є залучення засобів у банк, а у функції входять: облік депозитних засобів банку по їхній терміновості й окремих депонентах...
69361. Інформаційні системи фондового ринку 104 KB
  Учасниками фондового ринку є: емітенти цінних паперів юридичні й у деяких випадках передбачених законодавством фізичні особи що від свого імені випускають цінні папери і зобов’язуються виконувати обов’язки що випливають з умов їхнього випуску.
69362. Міжнародна електронна мережа та система електронних платежів НБУ 225.5 KB
  Для забезпечення організації і прискорення розрахунків на міжнародному рівні в НБУ застосований Центр міждержавних розрахунків. Згідно затвердженого Положення про Центр міждержавних розрахунків його основними завданнями є: прискорення міжнародних...
69363. Характеристика автоматизованих інформаційних систем 70.5 KB
  Існують інформаційна промисловість і національні інформаційні ресурси відбувається перехід від індустріальної економіки до економіки що ґрунтується на інформації. Під інформаційною технологією розуміють комплекс методів і процедур які реалізують функції збору...
69364. Економічна інформація та засоби її формалізації 70.5 KB
  Характеристика засобів формалізованого опису економічної інформації До числа основних засобів формалізованого опису елементів економічної інформації в ІС відносяться класифікація і кодування означених номенклатур по яким здійснюється упорядкування пошук та логічна обробка...
69365. Характеристика технологічних операцій та технологічних процесів оброблення економічної інформації 56.5 KB
  Методи контролю достовірності набору інформації. Головне для розподілу дій на окремі операції це їх логічне завершення яке веде до конкретного результату: нового носія інформації нового масиву файлу змінах у значеннях окремих атрибутів і т.