Ocena użytkownikóww: ***** / 3
Nadesłany przez Tomasz Lubiński, 09 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
floyd_c.cpp:
//(c)2002 Tomasz Lubinski
//www.algorytm.org
//algorytm Floyda - minimalne odleglosci miedzy wierzcholkami w grafie, domkniecie zwrotne
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <math.h>
//definicja funkcji min
#ifdef __cplusplus
double min (double value1, double value2);
double min (double value1, double value2)
{
return ( (value1 < value2) ? value1 : value2);
}
#endif
int i,j,k,n;
char tmp[100];
struct macierz
{
double odl; //odleglosc
int droga; //1 - droga istnieje; 0 - droga nie istnieje
}A[20][20];
void main()
{
clrscr();
printf("Podaj liczbe wierzcholkow\n");
scanf("%d", &n);
printf("Podaj wartosci macierzy odleglosci A\n");
printf("Gdy miedzy wierzcholkami nie ma polaczenia wpisz niesk\n");
//wczytanie od uzytkownika odleglosci
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
if (i==j) {A[i][j].odl=0; A[i][j].droga=1; continue;}
printf("A[%d,%d]=",i,j);
scanf("%s",tmp);
if (strcmp(tmp,"niesk"))
{A[i][j].odl=atof(tmp);
A[i][j].droga=1;}
else
{A[i][j].odl=0;
A[i][j].droga=0;}
}
//algorytm Floyda
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
if((A[i][k].droga==1)&&(A[k][j].droga==1))
{
if (A[i][j].droga==0)
A[i][j].odl=A[i][k].odl+A[k][j].odl; //jesli droga i,j nie istnieje to musi to byc suma drog i,k+k,j
else
A[i][j].odl=min(A[i][j].odl, A[i][k].odl+A[k][j].odl); //jesli istnieje to wybierz minimum z drog i,j oraz i,k+k,j
A[i][j].droga=1;
}
}
//wypisanie wynikow
for (i=0; i<n; i++)
{printf("\n");
for (j=0; j<n; j++)
if (A[i][j].droga==0) printf(" D[%d,%d]=niesk. ",i,j); else printf(" D[%d,%d]=%f",i,j,A[i][j].odl);}
getche();
}