4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

48 чел.

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»


 

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

55488. Понятие компьютерной публикации. Средства создания публикаций. Виды публикаций, их шаблоны. Структура публикаций 345.5 KB
  Цели: Образовательные: познакомить учащихся с понятием компьютерной публикации; с видами публикаций; с понятием шаблона публикации и ее структуры; со средствами создания публикации; научить учащихся: использовать программу Publisher...
55489. Компьютерные публикации на основе использования готовых шаблонов 1.23 MB
  Использовать макеты публикаций поставляемые с Publisher и модифицировать заготовку для создания собственной публикации. Как вы думаете какая программа из пакета MS Office наиболее подходит для создания публикаций Publisher.
55490. Здравствуй, Пушкин! 81.5 KB
  Цели: раскрыть духовный и художественный потенциал произведений А.С.Пушкина, их общечеловеческие нравственные ценности; развивать творческую деятельность учащихся, навыки выразительного чтения художественных текстов, высокие эстетические чувства, жизненную компетентность...
55491. А.С. ПУШКИН «СТАНЦИОННЫЙ СМОТРИТЕЛЬ» 164.5 KB
  Сравниваем литературных героев Какое содержание библейской притчи нашло отражение в повести Станционный смотритель и что автор изобразил по-своему
55493. Путешествуем с географией 59.5 KB
  Цели урока: познакомить учащихся с географической картой планеты и особенностями природы наших материков; воспитывать у учащихся интерес к знаниям, внимательность, заинтересованность; развивать умения и навыки работы с картами, дополнительной литературой.
55494. Пять уроков в PhotoShopе 3.98 MB
  Очень важно пройти весь путь от сканирования фотографии или ввода компьютерного изображения до его окончательного применения в практических целях докладах презентациях проектной работе. Для представления обработки и хранения изображения в компьютере...
55495. Характеристика методу навчання співробітництві варіант «Ажурна пилка» 112 KB
  Застосування методу робота в групах на уроках теоретичного навчання. Характеристика методу навчання співробітництві варіант Ажурна пилка8 Висновок. Одним із нових напрямків у підвищенні якості підготовки робітників і спеціалістів є технологічний підхід до навчання який полягає у повному управлінні навчальним процесом відтворенні усіх навчальних дій корекції навчального процесу оперативному зворотному звязку. Саме такій підхід є гарантією досягнення...
55496. Педагогическая деятельность. Психологический анализ урочной деятельности 105 KB
  Ответьте на следующие вопросы: В чем смысловое отличие термина психологический анализ урока от термина педагогический дидактический методический анализ урока С какой целью проводится психологический анализ урока...