第三次：第三题

>几点说明：
>- 由于六度的话计算比较麻烦不利于我自己检查，所以在本题中我统一使用“一度”，即使用`if(dis[i] > 1)`来判断，需要的话可以直接将这个一改为六即可。
>- 后来为了方便和高级，我使用`#define degree 1`来定义度数。
>- `matrix2.txt`文件见目录。
>- 这次的三个题其实是递进的，按顺序来的话应该可以看得出来，我的代码中有很多`printf`的操作，你可以适当的修改的删除，更格式什么的

```c
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define degree 1

void six_probability(int ** matrix, int size, int member);

int main(){
    int ** matrix;
    // read the file and get the matrix
    FILE * fp = fopen("matrix2.txt", "r");
    if(fp == NULL){
        printf("Open file error !\n");
        return 0;
    }
    int size, edges;
    int x, y;
    int i, j;
    fscanf(fp, "%d %d", &size, &edges);
    // printf("%d, %d\n", size, edges);
    matrix = (int **)malloc(sizeof(int *) * size);
    for(i = 0; i < size; i++){
        matrix[i] = (int *)malloc(sizeof(int) * size);
        for(j = 0; j < size; j++){
            matrix[i][j] = 0;
        }
    }
    for(i = 0; i <= edges; i++){
        fscanf(fp, "%d %d", &x, &y);
        matrix[x][y] = 1;
        matrix[y][x] = 1;
    }
    fclose(fp);
    // show the matrix
    for(i = 0; i < size; i++){
        for(j = 0; j < size; j++){
            printf("%d  ", matrix[i][j]);
        }
        printf("\n");
    }

// deal with it by djikstra
    for(i = 0; i < size; i++){
        six_probability(matrix, size, i);
    }

return 0;
}

// 计算概率
void six_probability(int ** matrix, int size, int member){
    int i;
    int * dis = (int *)malloc(sizeof(int) * size);
    int * flag = (int *)malloc(sizeof(int) * size);
    dis[member] = 0;
    flag[member] = 1;
    for(i = 0; i < size; i++){
        if(i == member){
            continue;
        }
        if(matrix[member][i] != 0){
            dis[i] = matrix[member][i];
            flag[i] = -1;
        }
        else{
            dis[i] = 9999;
            // means infinity
            flag[i] = 0;
        }
    }
    int min, min_num;
    min = 9999;
    while(1){
        // get min
        for(i = 0; i < size; i++){
            if(flag[i] == -1){
                if(dis[i] < min){
                    min = dis[i];
                    min_num = i;
                }
            }
        }
        flag[min_num] = 1;
        // if finished
        for(i = 0; i < size; i++){
            if(flag[i] != 1){
                break;
            }
        }
        if(i == size){
            break;
        }
        // reset dis
        for(i = 0; i < size; i++){
            if(flag[i] != 1){
                if(matrix[min_num][i] != 0){
                    if((min + matrix[min_num][i]) < dis[i]){
                        dis[i] = min + matrix[min_num][i];
                        flag[i] = -1;
                    }
                }
            }
        }
        // set min to 9999 max
        min = 9999;
    }

// print the result
    float probability = 0;
    int counter = 0;
    printf("The result of '%d' dot is : \n", member);
    for(i = 0; i < size; i++){
        printf("%d  ", dis[i]);
        if(dis[i] > degree){
            counter++;
        }
    }
    printf("\n");
    probability = (float)(size - counter - 1) / (float)(size - 1);
    printf("The probability of '%d' dot satisfies the six degrees of space theory is : %.2f %%.\n", member, probability * 100);

}
```