Лабораторная работа №1 (Задача 6)

Задача 6. На рис. 3 показана коммуникационная сеть между двумя приемно-передающими станциями 1 и 7. Возле каждой дуги этой сети указаны вероятности передачи сообщений без потерь по этим дугам. Необходимо найти маршрут от станции 1 к станции 7 с максимальной вероятностью успешной передачи сообщений. Сформулируйте эту задачу как нахождение кратчайшего пути и решите.

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

Кратчайший путь: 1-2-4-3-6-7

Вывод:

Маршрут 1-2-4-3-6-7 является маршрутом, с максимальной вероятностью передачи информации.

Листинг программы:

#include <math.h>

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

#define infinity 0.000000001

#define MAX 101

typedef unsigned sht;

sht w, v, n, m, s, t, p[MAX];

float c[MAX][MAX],d[MAX];

bool a[MAX];

void entering();

void print_small(sht );

sht mini();

int main()

{int i;

entering();

for(i = 1; i <= n; i++ ){

a[i] = false;

d[i] = (1-(c[s][i]));

p[i] = s;

};

a[s] = true;

d[0] = 1-infinity;

for( sht i = 1; i < n; i++ ){

w = mini();

a[w] = true;

for( sht j = 1; j <= n; j++ )

if( (a[j] == false )&&( d[w] + (1-(c[w][j]))<d[j]) ){

p[j] = w;

d[j] = d[w] + (1-(c[w][j]));

}

}

print_small( t );

getch();

return 0;

}

void entering(){

sht i, j, q1, q2;

float q;

FILE *input;

input=fopen("input.txt","r");

fscanf(input,"%d %d %d %d",&n,&m,&s,&t);

for(i = 1; i <= n; i++)

for(j = 1; j<=n; j++ )

if( i==j ) c[i][j] = infinity;

else

c[i][j] = infinity;

for( i = 1; i <= m; i++ ){

fscanf(input,"%d %d %f\n",&q2,&q1,&q);

c[q2][q1] = q;

};

fclose(input);

}

void print_small(sht r){

if( r!=s )

print_small(p[r]);

if( r==t )

cout<<r;

else

cout<<r<<" ";

}

sht mini(){

sht b=0;

for( sht i = 1; i <= n; i++ )

if(( a[i]==false )&&( d[i]<d[b] ))

b = i;

return b;

}

3