4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

41 чел.

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»


 

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

66208. Онкогенные вирусы. Особенности противоопухолевого иммунитета 113 KB
  Идея о возможной роли вирусов в возникновении рака была поддержана И. Опухолеродное действие вирусов на клетки принципиально отличается от инфекционного действия и процесс вирусного канцерогенеза не является инфекционным.
66209. ВИХОВАННЯ І ШКОЛА В ЕПОХУ СЕРЕДНЬОВІЧЧЯ 64.5 KB
  Навчання починали з механічного заучування на латині молитов і 150 псалмів а потім вивчали латинську азбуку читання і письмо. Виникла така форма навчання як учнівство. Найкращим методом навчання вважався пошук найкоротшого шляху досягнення знань.
66210. Технология найма и отбора персонала 79.5 KB
  Цель набора персонала состоит в создании резерва кандидатов на все рабочие места с учетом в том числе и будущих организационных и кадровых изменений увольнений перемещений уходов на пенсию окончаний сроков контрактов изменений направлений...
66211. Модель проектной группы MSF для небольших команд 66 KB
  Задачи ролевых групп Группа Управление программой : управляет процессом разработки с целью получения готового продукта в отведенные сроки; регулирует взаимоотношения и коммуникацию внутри проектной группы; следит за временным графиком проекта и готовит отчетность о его состоянии...
66212. СТАНОВЛЕННЯ І РОЗВИТОК ЗАРУБІЖНОЇ ПЕДАГОГІЧНОЇ НАУКИ І ПРАКТИКИ У 17 – 19 СТОЛІТТЯХ 71 KB
  Вона була незалежна від церкви і держави існувала на пожертвування і високу плату за навчання. Єдиних навчальних планів не було кожна школа складала програму навчання на власний розсуд. Уряди численних німецьких держав ставились вимоги до організації початкових шкіл у містах і селах навчання хлопчиків...
66213. Сущность и основные формы адаптации персонала 54.5 KB
  Организация процесса адаптации Понятие цели и основные направления адаптации После заключения трудового контракта человек приступает к выполнению трудовых обязанностей. При этом человек проходит через период адаптации.
66215. РЕФОРМАТОРСЬКА ПЕДАГОГІКА ЗАРУБІЖНИХ КРАЇН НАПРИКІНЦІ 19 – НА ПОЧАТКУ 20 СТОЛІТТЯ 86.5 KB
  Перед масовою народною школою постало завдання розробити нові форми навчання і виховання з метою підняття рівня освіти. При Феррі 1832-1893 було запроваджено автономію університетів розроблено нові навчальні плани середньої школи в яких більше уваги приділялось вивченню природничих наук...
66216. Деловая оценка персонала в организации 60.5 KB
  Структура процесса требования к проведению аттестации Понятие виды функции оценки персонала Деловая оценка – процесс определения эффективности деятельности сотрудников в ходе реализации задач организации. Объектом аттестации может быть отдельный сотрудник рабочее место соответствие его требованиям...