4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

53 чел.

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»


 

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

17193. ДОМАШНИЙ ДОКТОР ДЛЯ ДЕТЕЙ 2.06 MB
  Клафлин Эдвард под ред. ДОМАШНИЙ ДОКТОР ДЛЯ ДЕТЕЙ Советы американских врачей пер. Почиталин И. Г. Изд. КронПресс Москва 1997 г. OCR Палек Alligator 1998 г. Вступление Как помочь здоровью вашего ребенка Если у вас есть дети вы наверное захотите чтобы под рукой ...
17194. КРИЗИС БЕЗБОЖИЯ 68 KB
  И.Ильин КРИЗИС БЕЗБОЖИЯ Первая глава лекции прочитанной И.А. Ильиным в Риге 11 октября 1935 года. Историческое время выпавшее нам на долю исполнено великого и глубокого значения: это эпоха чрезвычайной насыщенности напряженности эпоха крушения подводящего...
17195. ПРЕДАНИЕ И ПРЕДАНИЯ 66.5 KB
  Лосский ПРЕДАНИЕ И ПРЕДАНИЯ Предание ParadosisTraditio один из терминов у которого так много значений что он рискует вовсе утерять свой первоначальный смысл. И это не только по причине некоторого обмирщения которое обесценило столько слов богословского словаря как дух...
17196. ТИПЫ РЕЛИГИОЗНОЙ ЖИЗНИ 96 KB
  Мать МАРИЯ Скобцова ТИПЫ РЕЛИГИОЗНОЙ ЖИЗНИ Если мы начнем изучать историческое место на котором мы находимся или вернее те исторические типы благочестия которые сейчас выработало наше историческое положение то мы сможем объективно и беспристрастно увидеть разн
17197. СПАСЕHИЕ И ОПРАВДАHИЕ 104 KB
  Аpхиепископ Михаил Мудьюгин СПАСЕHИЕ И ОПРАВДАHИЕ Опыт кpаткого pаскpытия пpавославной субъективной сотеpиологии Стpемление к спасению в будущей или загpобной жизни явление хаpактеpизующее духовную жизнь многих веpоятно даже большинства сознательных хpистиан. ...
17198. Замечания по поводу атеистической литературы последних лет 69 KB
  Замечания по поводуатеистической литературы последних лет. Внимательное ознакомление с весьма многочисленной антирелигиозной литературой привело меня к следующим выводам: 1. Эта литература поражает прежде всего своей невероятной отсталостью. В ней можно найти множ...
17199. О детском крещении 41 KB
  О детском крещении Что написано в Священном Писании о крещении Посмотрим основные места. 1 Мф.28:1920 Итак идите научите ВСЕ НАРОДЫ крестя их во имя Отца и Сына и Святого Духа уча их соблюдать все что Я повелел вам; и се Я с вами до скончани
17200. ПРАВОСЛАВНЫЙ ИНТЕРНЕТ В РОССИИ 114 KB
  ПРАВОСЛАВНЫЙ ИНТЕРНЕТ В РОССИИ СОДЕРЖАНИЕ: КАКИМ БУДЕТ ПРАВОСЛАВНЫЙ ИНТЕРНЕТ Москва 7 сентября Метафрасис Первая конференция посвященная перспективам развития православных ресурсов на русском языке в глобальной компьют...
17201. ПРАВОСЛАВИЕ В НОВЕЙШИХ ПЛЮРАЛИСТИЧЕСКИХ ОБЩЕСТВАХ 37.5 KB
  протопресвитер Фома Хопко ректор Св.Владимирской духовной семинарии НьюЙорк ПРАВОСЛАВИЕ В НОВЕЙШИХ ПЛЮРАЛИСТИЧЕСКИХ ОБЩЕСТВАХ доклад на Межправославной подготовнтельной консультации по Всемирной миссии и евангелизму Аддис Абеба январь 1996 г. Перевод с а