Поиск минимального пути по алгоритму Форда

↑

▷ Содержание

⇐ ПредыдущаяСтр 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);

}

Вывод: В этой работе были рассмотрены алгоритмы поиска кратчайших путей между вершинами в графе, а именно алгоритм Форда и алгоритм Беллмана-Калаба. Эти алгоритмы часто используются для решения многих задач.

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности