Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Поиск минимального пути по алгоритму Форда⇐ ПредыдущаяСтр 11 из 11
Алгоритм Форда позволяет от какой-либо исходной вершины Xi определить минимальный путь до произвольной вершины Xj графа G. Алгоритм Форда состоит из следующих шагов: 1) Каждой вершине Xi графа G ставятся в соответствие максимально возможные для данной задачи числа Hi; 2) На втором шаге вычисляются разности Hj-Hi для каждой вершины Xi, где Hj - вес вершины, в которую ведет дуга (Xi,Xj). Здесь возможны три случая: Hj - Hi < Lij, Hj-Hi=Lij, Hj-Hi>Lij, где Lij - вес дуги, ведущей из вершины Xi в вершину Xj. Случай, когда Hj-Hi>Lij позволяет нам уменьшить расстояние между вершинами Xi и Xj благодаря следующим преобразованиям: Hj-Hi>Lij, Hj > Lij + Hi, отсюда принимаем: Hj=Hi+Lij. Второй шаг выполняется до тех пор, пока еще существуют пары (i,j), для которых выполняется неравенство Hj-Hi>Lij. По окончанию второго этапа метки вершин позволяют нам определить значение минимального пути из исходной в конечную вершину; 3) На третьем этапе происходит определение минимального пути при помощи обратного хода от конечной вершины к начальной, причем для вершины Xj предшествующей будет вершина Xi, если для этой пары выполняется Hj-Hi=Lij. Если существует несколько таких пар, то выбирается любая из них.
Алгоритм Белмана - Калаба
Использование алгоритма Беллмана-Калаба позволяет нам ускорить поиск минимального пути между произвольной заданной парой вершин. На первом этапе заданному графу ставится в соответствие взвешенная матрица смежности M. Матрица формируется по следующим правилам: 1) M(i,j)=Lij, если существует дуга, ведущая из Xi в Xj, где Lij - вес этой дуги; 2) M(i,j)=max, где max - максимально возможное число для данной задачи, если не существует дуги, ведущей из вершины Xi в Xj; 3) M(i,j)=0, если i=j. На втором этапе строится вектор V0 по следующим правилам: 1) V0(i)=Lin, если существует дуга, ведущая из вершины Xi в вершину Xn, где Xn - конечная заданная вершина, для которой ищется минимальный путь, Lin - вес этой дуги; 2) V0(i)=max, где max - максимально возможное число для данной задачи, если не существует дуги, ведущей из вершины Xi в Xn; 3) V0(i)=0, если i=j. На k-той итерации строится вектор Vk по следующим правилам: 1) Vk(i)=min{Vk-1(j)+Lij}, где i=1..(n-1),j=1..n; i<>j 2) Vk(n) = 0. Итерации прекращаются, когда мы получаем вектор, равный предыдущему, т.е.Vk=Vk-1. После прекращения процесса элемент вектора Vk, имеющий наименьшее значение, не равное нулю, дает нам длину минимального пути между заданной парой вершин.
4 Кратчайшие пути: 1 3 4 3 из 1 в 2 - 1->2 (длина 2); из 1 в 3 - 1->2->3 (длина 3); 2 2 5 из 1 в 4 - 1->4 (длина 2); 2 19 2 из 1 в 5 - 1->4->5 (длина 5); из 1 в 6 - 1->2->3->4->5->6 (длина 12). 1 6
Исходный код программы поиска кратчайших путей с использованием каждого из выше приведенных алгоритмов:
#include <stdio.h> #include <conio.h> #include <alloc.h>
#define MAX 30000
struct List{ int v; int w; struct List *next; }; struct Graph{ int h; int p; struct List *first; struct List *last; }*G;
int N; int V;
void Ford(); void BelmanKalab(); void PathFord(int); void Menu(); void ListAdj(); void FreeList();
void main() { Menu(); }
void BelmanKalab() { int i,j,k; struct List *c; int **M=(int **)malloc(N*sizeof(int *)); int *VK=(int *)malloc(N*sizeof(int)); int *VK_1=(int *)malloc(N*sizeof(int)); int *t,f=1; int *P=(int *)malloc(N*sizeof(int)); for(i=0;i<N;i++) M[i]=(int *)malloc(N*sizeof(int)); for(i=0;i<N;i++) for(j=0;j<N;j++) M[i][j]=(i==j)?0:MAX; for(i=0;i<N;i++){ c=G[i].first; while(c!=G[i].last){ M[i][c->v]=c->w; c=c->next; } } printf("Enter final vertex: "); scanf("%d",&V); V--; for(i=0;i<N;i++){ VK_1[i]=M[i][V]; P[i]=-1; } while(f){ for(i=0;i<N;i++) VK[i]=MAX; for(i=0;i<N;i++) for(j=0;j<N;j++) if(i!=j && VK[i]>VK_1[j]+M[i][j]){ VK[i]=VK_1[j]+M[i][j]; P[i]=j; } VK[V]=0; for(i=0;i<N && VK[i]==VK_1[i];i++) ; f=(i==N)?0:1; t=VK_1; VK_1=VK; VK=t; } for(i=0;i<N;i++){ printf("\nPath from %d to %d is ",i+1,V+1); if(VK_1[i]==MAX) printf("not exist."); else { for(k=i,j=0;j<N && P[k]!=-1 && k!=V;j++){ printf("->%d",k+1); k=P[k]; } printf("->%d",V+1); printf(". It has length %d.",VK_1[i]); } } for(i=0;i<N;i++) free(M[i]); free(P); free(M); free(VK); free(VK_1); }
void Ford() { int i,f=1; struct List *c; if(G==NULL) return; for(i=0;i<N;i++){ G[i].p=-1; G[i].h=MAX; } printf("Enter start vertex: "); scanf("%d",&V); G[--V].h=0; while(f){ f=0; for(i=0;i<N;i++){ c=G[i].first; while(c!=G[i].last){ if(G[c->v].h>G[i].h+c->w){ G[c->v].h=G[i].h+c->w; G[c->v].p=i; f=1; } c=c->next; } } } for(i=0;i<N;i++){ printf("\nPath from %d to %d is ",V+1,i+1); if(G[i].h==MAX) printf("not exist."); else{ PathFord(i); printf(". It has length %d.",G[i].h); } } }
void PathFord(int v) { if(v!=V) PathFord(G[v].p); printf("->%d",v+1); }
void Menu() { int i; char ch; clrscr(); printf("1.To enter the graph\n"); printf("2.Minimum path by Ford's algorithm\n"); printf("3.Minimum path by Belman-Kalab's algorithm\n"); printf("4.Exit\n"); do ch=getch(); while(ch<'0' || ch>'5'); clrscr(); switch (ch) { case '1': ListAdj();break; case '2': Ford();getch();break; case '3': BelmanKalab();getch();break; case '4': FreeList();return;
} Menu(); }
void ListAdj() { int i,v,w; struct List *c; if(G) FreeList(); printf("Enter number of vertexes of graph: "); scanf("%d",&N); G=(struct Graph *)malloc(N*sizeof(struct Graph)); printf("\n"); for(i=0;i<N;i++){ printf("%d->",i+1); G[i].first=(struct List*)malloc(sizeof(struct List)); G[i].last=G[i].first; G[i].last->next=NULL; G[i].last->v=-1; scanf("%d",&v); while(v){ scanf("%d",&w); G[i].last->v=v-1; G[i].last->w=w; G[i].last->next=(struct List*)malloc(sizeof(struct List)); G[i].last=G[i].last->next; G[i].last->next=NULL; G[i].last->v=-1; scanf("%d",&v); } } }
void FreeList() { struct List *c,*t; while(N--){ c=G[N].first; while(c!=G[N].last){ t=c->next; free(c); c=t; } } free(G); }
Вывод: В этой работе были рассмотрены алгоритмы поиска кратчайших путей между вершинами в графе, а именно алгоритм Форда и алгоритм Беллмана-Калаба. Эти алгоритмы часто используются для решения многих задач.
|
||||||
Последнее изменение этой страницы: 2017-02-07; просмотров: 412; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.169.110 (0.024 с.) |