4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

38 чел.

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»


 

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

41390. Базы данных Snаpshot. Snаpshot: моментальный снимок базы данных 72.5 KB
  Snpshot: предназначен для хранения архивных данных Пример Аудит: мероприятия операции направленные на отслеживание изменений базы данных кто когда как.
41391. Базы данных. Основы SQL. Реляционная база данных 120 KB
  SQL Structured Query Lnguge: 1970гг впервые разработан IBM для System R назывался SEQUEL; первый стандарт NSI SQL 1986г; первая коммерческая СУБД поддерживающая SQL была Orcle V2 на машинах VX. SQL 92: SQL 2 ISO 9075 SQL 99: SQL 3 объектноориентированные возможности. SQL 2003 SQL 2006 SQL 2009: XML.
41392. Базы данных SQL. Создание таблиц. 138.5 KB
  Заполнение таблиц Секция WHERE SELECT DELETE UPDTE Ограничение ссылочной целостности CONSTRINT SELECT ORDER BY SELECT TOP SELECT DISTINCT WHERE BEWEEN WHERE IS NULL WHERE NOT WHERE LIKE GROUP BY.
41394. Базы данных SQL 121.5 KB
  LEFT OUTER JOIN RIGHT OUTER JOIN FULL OUTER JOIN INSERT INSERT SELECT INSERT UNIQUEIDENTIFIER IDENTITY INSERT defult deciml вычисляемые столбцы Время дата .
41395. Базы данных. Индексы 126 KB
  Индекс: всегда связан с таблицейс подмножеством столбцов таблицы. Индекс: предназначен для ускорения поиска строк в таблице по индексируемым столбцам Индекс: Microsoft SQL Server бывают кластерные некластерные просто индексы. Некластерный индекс: физически находится отдельно от таблицы список значений индексируемого столбца столбцов в определенном порядке с указателем на строку в таблице; список как правило бинарное дерево поиска.
41397. Базы данных. Повышение производительности запроса. 359 KB
  Query Optimizer: вычисляет несколько планов не все запроса на основе статистики метаданных информации о индексах и др.; на основе статистики предполагает стоимости запроса по различным планам и выбирает план с минимальными затратами на использование ресурсов помещает его кэш; как правило планы хранящиеся в кэше используются повторно. Стоимость запроса: числовая величина характеризующая степень использования ресурсов; Эффективность плана: наличие индексов или сканирование; статистика о распределении данных как правило...
41398. Базы данных. Программные интерфейсы с базой данных 483 KB
  ADO.NET: архитектура, модель поставщиков данных (провайдеров) ADO.NET: Data Provider - набор классов ADO.NET, позволяющих получить доступ к базе определенного типа (MS SQL Server, Oracle, DB2, MySQL) данных (выполнять sql-команды, и извлекать данные). ADO.NET: Data Provider включает следующие классы: