4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

46 чел.

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»


 

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

37918. Изучение Эффекта Холла 240.5 KB
  Эффект Холла Изучение зависимости холловской разности потенциалов от величины силы тока JД в датчике Холла [3. Контрольные вопросы [5] Список литературы Лабораторная работа № 56 Изучение Эффекта Холла 1.
37919. ИЗУЧЕНИЕ ВИХРЕВОГО ЭЛЕКТРИЧЕСКОГО ПОЛЯ 310.5 KB
  ЛАБОРАТОРНАЯ РАБОТА № 57 ИЗУЧЕНИЕ ВИХРЕВОГО ЭЛЕКТРИЧЕСКОГО ПОЛЯ Цель работы Изучение явления электромагнитной индукции и свойств вихревого электрического поля. Уравнение Максвелла для электрического поля В 1931 году М.1 Анализируя явление электромагнитной индукции Максвелл установил что причиной появления ЭДС индукции является возникновение в контуре электрического поля.
37920. ИЗУЧЕНИЕ МАГНИТНОГО ПОЛЯ ПРЯМОЛИНЕЙНОГО ТОКА 338.5 KB
  Шатохин Изучение магнитного поля прямолинейного тока. Детально рассмотрены характеристики магнитного поля прямолинейного тока. Изложена методика экспериментального определения магнитного поля токонесущих проводников.
37921. ИЗУЧЕНИЕ ИНТЕРФЕРЕНЦИИ СВЕТА 723.5 KB
  Сагитова Изучение интерференции света: Методические указания к лабораторной работе № 61 по курсу общей физики Уфимск. Методические указания знакомят студентов с явлением интерференции света методами получения когерентных волн.4 Порядок выполнения работы [8] 4 Контрольные вопросы [9] Список литературы Лабораторная работа № 61 ИЗУЧЕНИЕ ИНТЕРФЕРЕНЦИИ СВЕТА 1 Цель работы Изучение явления интерференции света.
37922. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЕЙ ПРЕЛОМЛЕНИЯ ЖИДКИХ И ТВЕРДЫХ ТЕЛ 235.5 KB
  Сагитова Определение показателей преломления жидких и твердых тел: Методические указания к лабораторной работе №62 по разделу Оптика Уфимск. Приведены краткая теория и методы измерения показателя преломления жидких и твердых тел.1 Определение показателя преломления стекла с помощью микроскопа [2.
37923. ИЗУЧЕНИЕ ОПТИЧЕСКИХ ХАРАКТЕРИСТИК ДИФРАКЦИОННОЙ РЕШЕТКИ 1.57 MB
  Изучение оптических характеристик дифракционной решетки. Студенты экспериментально определяют угловую дисперсию и разрешающую способность в различных порядках спектра фазовой дифракционной решетки.4 Оптические характеристики дифракционной решетки 10 3 Экспериментальная часть 13 3.
37924. ЭКСПЕРИМЕНТАЛЬНОЕ ИЗУЧЕНИЕ ЗАКОНОВ ТЕПЛОВОГО ИЗЛУЧЕНИЯ 2.24 MB
  Краузе Экспериментальное изучение законов теплового излучения: Методические указания к лабораторной работе № 64 по курсу общей физики Уфимск. Методические указания знакомят студентов с явлением теплового излучения. Описаны физические причины излучения электромагнитных волн нагретыми телами и приведены законы которым это излучение подчиняется.
37925. Изучение законов постоянного тока Исследование зависимости КПД источника тока от сопротивления нагрузки 383 KB
  Лабораторная работа № 33 Изучение законов постоянного тока Исследование зависимости КПД источника тока от сопротивления нагрузки 1. Определить КПД источника тока. Получить экспериментальную зависимость мощности источника тока от сопротивления нагрузки.
37926. Изучение явления термоэлектронной эмиссии и определение удельного заряда электрона 206.5 KB
  Благодаря пространственному заряду при малых анодных напряжениях анодный ток может быть значительно меньше возможного тока эмиссии катода и постепенно увеличивается при повышении анодного напряжения. Если поддерживать температуру накаленного катода постоянной и снять зависимость анодного тока Iа от анодного напряжения uа – вольт амперную характеристику рис.2 Вольт амперные характеристики диода при различных температурах T2  T1 Зависимость термоэлектронного тока Iа от анодного напряжения в области малых положительных значений uа...