Словестный алгоритм действий.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В Г. ТАГАНРОГЕ
(ТТИ Южного федерального университета)
Факультет автоматики и вычислительной техники
Кафедра систем автоматизированного проектирования
ОТЧЕТ
по лабораторной работе №2
Дисциплина: Теория графов и гиперграфов
Тема: «Алгоритм Форда и Дейкстра»
Выполнил:
Ст-т. группы А-71
Субоч В.С
Преподаватель:
Щеглов С.Н.
Таганрог 2012
Маршруты, цепи, циклы. Определения и примеры.
Маршрутом в графе G = (X, U) называется некоторая конечная последовательность ребер вида S = (х0, х1), (x1, х2), ..., (х(l-I) , x(l)), где х(о), х(l) - соответственно его начальная и конечная вершины. Очевидно, что в конечном графе G можно выделить только конечное число маршрутов. Число ребер в маршруте S называется его длиной. Существует простой способ определения маршрутов длиной q по матрице R графа G путем возведения ее в q-ю степень.
Например, пусть задана матрица R графа G
Построим граф
 |
Рисунок 1 – пример графа
Возведение матрицы в степень производится путем поэлементного перемножения строки на столбец с суммированием полученных сомножителей. Маршрут, в котором нет повторяющихся ребер, называется цепью.
Получим:
Замкнутая цепь, в которой х0 = х1, называется циклом.
Соответственно цепи и циклы называются простыми, если они не содержат повторяющихся вершин, кроме, разумеется, первой и последней в случае цикла. В графе G
S1 = (x1, х2), (х2, х3), (х3, х4),(х4,х1),(х1,х2) - маршрут
S2 = (х1, х2), (х2, х3), (х3, х4), (х4, х1) – цикл
 |
Рисунок 2 – граф
S3= (х1,х2)(х2,х3)(х3,х4) – простой цикл
S4= (х1,х2)(х2,х4)(х4,х5)(х5,х3)(х3,х2)(х2,х4) – цепь.
Цикл длиной 3 называется треугольником.
Произвольный граф. Найти кратчайшие по стоимости пути между всеми вершинами графа. Метод Форда
Словестный алгоритм действий.
1) Строим матрицу R взвешенного графа G
Фиксируем одну вершину xk и приписываем V(k) = 0, а все м остальным V(n) = M.
2) За начало принимаем 1 вершину xi. Делаем проверку
V(j) > V(i) + rij. Если выполняется то заменяем V(j) на сумму V(i) + rij.
3) Выполняем пункты 1,2 пока все вершины не будут рассмотренны.
4) Конец алгоритма.
Построить структурную схему алгоритма Форда.
#include <iostream>
using namespace std;
int main()
{
const int n = 9;
int m[n][n] = { {0,3,0,6,0,0,0,7,3},
{3,0,5,0,0,0,0,9,11},
{0,5,0,8,6,0,0,0,12},
{6,0,8,0,3,0,14,10,5},
{0,0,6,3,0,2,4,6,0},
{0,0,0,0,2,0,15,13,0},
{0,0,0,14,4,15,0,1,0},
{7,9,0,10,6,13,1,0,3},
{3,11,12,5,0,0,0,3,0}};
int V[n],xk,cache;
xk = m[0][0];
for(int j = 0; j < n; j++)
{
if(j == 0)
V[j] = xk;
else
V[j] = -1;
}
for(int i = 0; i < n; i++)
{
for(int j =i; j < n; j++)
{
if(m[i][j] != 0)
{
if(V[j] == -1)
{
V[j] = V[i] + m[i][j];
}
else
if( V[j] < V[i] + m[i][j])
break;
else
V[j] = V[i] + m[i][j];
/*else
if(cache < V[j])
V[j] = V[i] + m[i][j];
else
V[j] = m[i][j];*/
}
}
}
for(int i =0; i < n; i++)
cout << V[i] << " ";
return 0;
}
Произвольный граф. Найти кратчайшие по стоимости пути между всеми вершинами графа. Метод Дейкстры.
Словестный алгоритм действий.
1. l(s) = 0, а осталные l(xi) = -1 для всех xi != s и считаем их пометки временные.
2. l(xi) <- min[l(xi); l(p) + r(p,xi)] – блок превращения прметки в постоянную.
3. Среди всех вершин найти такую, что l(xi) = min[l(xi)]/
4. xi считать постоянной и положить p = xi.