電網導作業3

hw3.c

#include <stdio.h>
#include <string.h>
void init(int d[9][9])
{   for (int i = 0; i < 9; ++i) 
        for (int j = 0; j < 9; ++j)
            d[i][j] = (i == j) ? 0 : -1;
    
    d[0][1] = 4; d[0][7] = 8;
    d[1][0] = 4; d[1][7] = 11; d[1][2] = 8;
    d[2][1] = 8; d[2][8] = 2;  d[2][3] = 7; d[2][5] = 4;
    d[3][2] = 7; d[3][4] = 9;  d[3][5] = 14;
    d[4][3] = 9; d[4][5] = 10;
    d[5][2] = 4; d[5][3] = 14; d[5][4] = 10; d[5][6] = 2;
    d[6][5] = 2; d[6][7] = 1; d[6][8] = 6;
    d[7][0] = 8; d[7][1] = 11; d[7][8] = 7; d[7][6] = 1;
    d[8][2] = 2; d[8][6] = 6; d[8][7] = 7;
    
}

void print(int d[9][9])
{   for (int i = 0; i < 9; ++i)
    {   printf("D%d(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) = (", i);
        for (int j = 0; j < 9; ++j)
        {   if (j) printf(", ");
            if (d[i][j] == -1)
                printf("\u221E");
            else
                printf("%d", d[i][j]);
        }
        printf(")\n");
    }
}

void solve(int e[9][9], int d[9][9]) // Bellman-Ford
{   
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            d[i][j] = (i == j) ? 0 : -1;

    for (int u = 0; u < 9; ++u)  // For each node
    {   for (int t = 0; t < 9-1; ++t)
            for (int i = 0; i < 9; ++i)
                    for (int j = 0; j < 9; ++j)
                        if (e[i][j] != -1 && d[u][i] != -1)
                        {   if (d[u][j] == -1 || d[u][i] + e[i][j] < d[u][j])
                            {
                                d[u][j] = d[u][i] + e[i][j];
                            }
                        }
    }
}

void dv(int e[9][9], int d[9][9])  // Distance Vector simulation
{
    int prev_d[9][9];
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            prev_d[i][j] = d[i][j] = e[i][j];


    int update = 0;
    do {  
        update = 0;
        for (int u = 0; u < 9; ++u)
        {   for (int v = 0; v < 9; ++v)  d[u][v] = prev_d[u][v];
    
    
            for (int v = 0; v < 9; ++v)
                if (e[u][v] > 0) // Not myself, and my neighbour
                {   for (int k = 0; k < 9; ++k) // Only update by information passed by neighbour
                        if (prev_d[v][k] != -1)
                        {   if (d[u][k] == -1 || d[u][v] + prev_d[v][k] < d[u][k])
                            {
                                d[u][k] = d[u][v] + prev_d[v][k];
                                update = 1;
                            }
                        }
                }
             
        }

        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                prev_d[i][j] = d[i][j];
    } 
    while(update);
    
}


int main()
{
    int e[9][9], d[9][9], k[9][9];
    init(e);
    print(e);
    solve(e, d);
    printf("Solved:\n");
    print(d);
    dv(e, k);
    printf("Hello\n");
    print(k);
    return 0;
}