Informatika gyűjtemény

Egy szinttel feljebb szerkezetek.cpp

2004050607080910

<<  8. óra - Floyd-Warshall algoritmus  >>

<<  Szerkezetek  >>

NézetNyomtat

szerkezetek.cpp (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
#define IFile "new13i.txt"
#define OFile "new13o.txt"
#define inf 1000
#include <stdio.h>
#include "matrix.h"

/*
    Gráf legrövidebb útjainak keresése bármely i és j csúcs között
    a Floyd-Warshall algoritmus alapján.
    A programot Uray M. János készítette 2008. november 11-én.
*/

inline type min (type A, type B) {
    return A > B ? B : A;
}
void print (const cMatrix &);
cMatrix Dist (const cMatrix &);
cMatrix Dist (const cMatrix &, int);

int main (void) {
    printf("<-- Start -->\n");
    cMatrix M, D;
    int I, J, K, G, R, A, B, bImp, Min, Max, H = 0;
    FILE * IF = fopen(IFile, "rt"), * OF = fopen(OFile, "wt");

    if (IF == NULL || OF == NULL)
        return 1;

    while (1) {
        fscanf(IF, "%d %d\n", &G, &R);
        if (!G)
            break;
        M.Set(G, G);
        M.Empty();
        for (I = 0; I < R; I++) {
            fscanf(IF, "%d %d\n", &A, &B);
            M.SetItem(A, B, 1);
            M.SetItem(B, A, 1);
        }
        D = Dist(M);
        bImp = 0;
        for (I = 0; I < G; I++)
            for (J = 0; J < G; J++)
                for (K = 0; K < G; K++)
                    if (D.GetItem(I, J) == D.GetItem(I, K) && D.GetItem(J, K) == 1)
                        bImp = 1;
        if (bImp)
            fprintf(OF, "impossible");
        else {
            Min = inf;
            for (I = 0; I < G; I++) {
                Max = 0;
                for (J = 0; J < G; J++)
                    if (D.GetItem(I, J) > Max)
                        Max = D.GetItem(I, J);
                if (Max < Min)
                    Min = Max;
            }
            fprintf(OF, "%d", Min);
        }
    }
    fclose(IF);
    fclose(OF);

    return 0;
}

void print (const cMatrix & A) {
    int I, J;

    for (I = 0; I < A.GetN(); I++) {
        for (J = 0; J < A.GetM(); J++)
            printf("%u ", A.GetItem(J, I));
        printf("\n");
    }
}

// Floyd-Marshall algoritmus
cMatrix Dist (const cMatrix & Graph) {
    cMatrix Q = Graph;
    int N = Graph.GetN();

    if (!Graph.bSquare())
        return Q;
    for (int I = 0; I < N; I++)
        Q = Dist(Q, I);
    return Q;
}
cMatrix Dist (const cMatrix & D, int K) {
    int I, J;
    cMatrix Q = D;

    for (I = 0; I < D.GetN(); I++)
        for (J = 0; J < D.GetM(); J++)
            Q.SetItem(J, I, min(D.GetItem(J, I),
                D.GetItem(K, I) + D.GetItem(J, K)));
    return Q;
}
(Vissza)