4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

43 чел.

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»


 

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

61176. ВІДОКРЕМЛЕНІ Й НЕВІДОКРЕМЛЕНІ ОЗНАЧЕННЯ, СПОСОБИ ЇХ ВИРАЖЕННЯ 59 KB
  Актуалізація мотиваційних резервів учнів з теми Творче спостереження з елементами аналізу Прочитати виразно текст додержуючись відповідної інтонації в ускладнених реченнях. Назвати речення ускладнені: а однорідними членами; б вставними словами; в відокремленими членами.
61177. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ОЗНАЧЕННЯМИ 203 KB
  Удосконалити в учнів загальнопізнавальні вміння правильно інтонувати речення з відокремленими й невідокремленими означеннями, пунктуаційні вміння й навички, пов’язані з уживанням розділових знаків у реченнях з відокремленими означеннями
61178. ВІДОКРЕМЛЕНІ ПРИКЛАДКИ 327 KB
  Виділити відокремлені прикладки. Алгоритм характеристики відокремленої прикладки Дослідження-трансформація Подані речення трансформувати так щоб виділені компоненти виступали в ролі відокремленої прикладки. Виділити відокремлені прикладки.
61179. ВІДОКРЕМЛЕНІ ДОДАТКИ. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ДОДАТКАМИ 217.05 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з відокремленими додатками, їх місцем у реченні; формувати загальнопізнавальні вміння знаходити в тексті відокремлені додатки, аналізувати їх, правильно інтонувати речення з відокремленими додатками
61180. ВІДОКРЕМЛЕНІ ОБСТАВИНИ, СПОСОБИ ЇХ ВИРАЖЕННЯ 131.02 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з основними способами морфологічного вираження відокремлених обставин, їх місцем у реченні відповідно до опорного слова; формувати загальнопізнавальні вміння знаходити в тексті відокремлені обставини
61181. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З ВІДОКРЕМЛЕНИМИ ОБСТАВИНАМИ 163.98 KB
  Удосконалити в учнів загальнопізнавальні вміння правильно інтонувати речення з відокремленими обставинами, пунктуаційні вміння й навички, пов’язані з уживанням розділових знаків у реченнях з відокремленими обставинами
61182. ПИСЬМОВИЙ ТВІР-ОПОВІДАННЯ З ОБРАМЛЕННЯМ НА ОСНОВІ ПОЧУТОГО 142 KB
  Довести що висловлювання належить до оповідання. Яку структуру має текст-оповідання Виділити в тексті обрамлення і з’ясувати яку функцію воно виконує у структурі оповідання. Формування вмінь моделювати твіроповідання з обрамленням Уведення у висловлювання обрамлення Прочитати мовчки текст.
61183. ВІДОКРЕМЛЕНІ УТОЧНЮВАЛЬНІ ЧЛЕНИ РЕЧЕННЯ. РОЗДІЛОВІ ЗНАКИ В РЕЧЕННЯХ З УТОЧНЮВАЛЬНИМИ ЧЛЕНАМИ 403.78 KB
  Поглибити знання восьмикласників про відокремлені члени речення, ознайомити з уточнювальними членами речення, їх основними способами морфологічного вираження, видами та значенням; сформувати загальнопізнавальні вміння знаходити в тексті відокремлені уточнювальні члени
61184. УЗАГАЛЬНЕННЯ Й СИСТЕМАТИЗАЦІЯ З ТЕМИ «ВІДОКРЕМЛЕНІ ЧЛЕНИ РЕЧЕННЯ» 503.5 KB
  Правопис: розділові знаки в реченнях з відокремленими членами. Текст риторичний аспект: використання відокремлених членів речення в усному й писемному мовленні. Яку функцію в реченні виконують відокремлені члени речення.