algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Floyda - Implementacja w C/C++
Ocena użytkownikóww: *****  / 3
SłabyŚwietny
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();
}
Dodaj komentarz