Курсовая работа: Поиск оптимального пути в ненагруженном орграфе
Множество 
называется фронтом волны kго уровня.
Вершины 
могут быть выделены неоднозначно, что соответствует случаю, если 
несколько минимальных путей из 
в 
.
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_34 минимальных расстояний R(D)между его вершинами. Это квадратная матрица размерности 
, элементы главной диагонали которой равны нулю (
, i=1,..,n).
Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (
, если 
). Далее построчно заполняем матрицу следующим образом.
Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i-тая и на пересечении с j-тым столбцом стоит единица (то есть 
). Это значит, что из вершины 
можно попасть в вершину 
за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент 
. Тогда из вершины в вершину 
можно попасть за два шага. Таким образом, можно записать 
. Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
Листинг программы:
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int N=0,n=0,c=0,i=0,k=0;
cout<<" ----------------------------------------------"<<endl;
cout<<" |Poisk optimalnogo puti v nenagrujennom orgrafe|"<<endl;
cout<<" ----------------------------------------------"<<endl;
case1:
cout<<"Vvedite chislo vershin v orgrafe: ";
cin>>N;
if(N<=1)
{
cout<<"Kolichestvo vershin doljno bit'>1!!!"<<endl;
goto case1;
}
///МАТРИЦАсмежности::
cout<<"Zapolnite matricu smejnosti (esli puti net,vvedite 0; esli put' est',vvedite 1):";
float** A = new float*[N];
for(i;i<N;i++)
A[i] = new float[N];
for(i=0;i<N;i++)