4573

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

Курсовая

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

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

Русский

2012-11-22

151 KB

61 чел.

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»


 

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

24860. Синергетический эффект как рез-т слияния и поглощения 30.5 KB
  Отделение подразумевает передачу части активов и обязательств новому предприятию с последующим предоставлением акционерам материнского предприятия акций нового предприятия пропорционально их доле собственности в первоначальном предприятии. Разбивка все активы реструктурируемого предприятия разделяются между отделяемыми предприятиями и материнское предприятие перестает существовать. В данном случае материнское предприятие учреждает новое предприятие и предает ему свои активы затем продает акции нового предприятия. Данный метод...
24861. Сравнительная характеристика базовых подходов к оценке стоимости бизнеса 30.5 KB
  Существуют 3 подхода к оценке стоимости любого объекта: 1 доходный который опирается на доходность потенциально возможную к получению в будущем; 2 затратный при котором стоимость рассматривается с точки зрения понесенных издержек; 3 сравнительный рыночный при котором возможно получение стоимости оцениваемого объекта через механизм сравнения данного объекта с объектами аналогами. Определение стоимости в данном случае осуществляется по фактически проведенным сделкам. В рамках доходного подхода существуют следующие методы определения...
24862. Сравнительная характеристика типов реструктуризации 25.5 KB
  Основной причиной почему компании стремятся к реструктуризации обычно является низкая эффективность их деятельности которая выражается в неудовлетворительных финансовых показателях в нехватке оборотных средств в высоком уровне дебиторской и кредиторской задолженности. В зависимости от целевых установок и стратегии компании определяется одна из форм реструктуризации: оперативная или стратегическая. Оперативная реструктуризация способствует улучшению результатов деятельности предприятия в краткосрочном периоде и создает предпосылки для...
24863. Средневзвешенная стоимость капитала 29.5 KB
  Если организация финансируется только за счет собственного капитала то стоимость капитала определяется как норма прибыли которую компания предлагает за свои ценные бумаги для поддержания их рыночной стоимости. В случае смешанного финансирования стоимость капитала рассчитывается как средневзвешенная величина составных частей капитала. Средневзвешенная стоимость капитала является основным показателем характеризующим стоимость капитала WACC = S Wj ∙ Kj где WACC средневзвешенная стоимость капитала Wj удельный вес капитала jного вида...
24864. Стоимость акционерного капитала на основе модели дисконтированного денежного потока (модель Гордона) 26.5 KB
  Этот темп отражает перспективы развития бизнеса и должен быть заложен в расчёт цены акционерного капитала Сакц=Д Р1Lд дтемп прироста дивидендов. Предприятиеэмитент может не планировать прирост дивидендов а заложить в свои расчёты прогнозы более сложного уровня. Эти прогнозы могут найти отражение в самом ожидаемом размере дивидендов.
24865. Стоимость лицензии: обоснование, расчёт 30.5 KB
  Оценка лицензии необходима при: 1.куплепродаже лицензии; 2.внесении лицензии в уставный капитал; 3.
24866. Стоимость СК в виде НРП 26 KB
  Нераспределенная прибыль принадлежит владельцам обыкновенных акций и может быть направлена на реинвестирование или не выплату дивидендов.
24867. Стоимость СК в виде обыкновенных акций 27 KB
  Модель оценки стоимости обыкновенных акций будет выглядеть следующим образом. Кs = Кrf Км Кrf β Кs цена обыкновенных акций как источник финансирования. β коэффициент характеризующий меру изменчивости акций предприятия относительно среднего курса акций на рынке.
24868. Расследование и учет несчастных случав на производстве 166 KB
  Социальное страхование от несчастных случаев и профессиональных заболеваний. Основные положения Закона Украины Об общеобязательном государственном социальном страховании от несчастного случая на производстве и профессионального заболевания, повлекшие утрату трудоспособности. Основные требования Порядка расследования и учета несчастных случаев, профессиональных заболеваний и аварий, на производстве.