//
//  main.cpp
//  
//  DijkstraFloyd
//
//  Created by vincent on 2017/11/07.
//  Copyright  2017 vincent. All rights reserved.
//

#include 
#include 
#include 
const int M = 65535; // M
const int SIZE = 9; // 

int G[SIZE][SIZE] = {
//  0   1   2   3   4   5   6   7   8
    0,  1 , 5,  M,  M,  M,  M,  M,  M,  // 0
    1,  0,  3,  7,  5,  M,  M,  M,  M,  // 1
    5,  3,  0,  M,  1,  7,  M,  M,  M,  // 2
    M,  7,  M,  0,  2,  M,  3,  M,  M,  // 3
    M,  5,  1,  2,  0,  3,  6,  9,  M,  // 4
    M,  M,  7,  M,  3,  0,  M,  5,  M,  // 5
    M,  M,  M,  3,  6,  M,  0,  2,  7,  // 6
    M,  M,  M,  M,  9,  5,  2,  0,  4,  // 7
    M,  M,  M,  M,  M,  M,  7,  4,  0,  // 8
};

void dijkstra() {
    int finals[SIZE]; // finals[w] = 1v0vw
    int lowcost[SIZE]; // v0
    int path[SIZE]; // 
    for(int i = 0; i < SIZE; ++i) printf("%d\t", i);
    printf("\n-------------------------------------------------------\n");
    
    for(int i = 0; i < SIZE; ++i) {
        finals[i] = 0; // finals
        lowcost[i] = G[0][i]; // v0
        path[i] = 0;
        printf("%d\t", lowcost[i]);
    }
    printf("\n");
    finals[0] = 1; // v0v0
    for (int i = 1; i < SIZE; ++i) {
        int min = M;
        int minIndex = 0;
        for (int j = 0; j < SIZE; ++j) {
            // v0
            if (finals[j] == 0 && lowcost[j] < min) {
                min = lowcost[j];
                minIndex = j;
            }
        }
        finals[minIndex] = 1; // finals1
        for (int j = 0; j < SIZE; ++j) {
            // v1vx+v0v1v0vx
            if (finals[j] == 0 && min + G[minIndex][j] < lowcost[j]) {
                lowcost[j] = min + G[minIndex][j];
                path[j] = minIndex;
            }
        }
        for(int j = 0; j < SIZE; ++j) printf("%d\t", lowcost[j]);
        printf("\n");
    }
    
    int target = 8;
    int sum = 0;
    printf("v%dv0", target);
    while (target != 0) {
        int pre = path[target];
        sum += G[target][pre];
        target = pre;
        printf("-> %d ", target);
    }
    printf("\n%d\n\n", sum);
}

void floyd() {
    int D[SIZE][SIZE]; // G
    int P[SIZE][SIZE]; // 
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            D[i][j] = G[i][j];
            P[i][j] = j;
        }
    }
    
    // D[x][y] = min(D[x][y], D[x][i] + D[i][y]
    // i(i=0~8)
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            for (int k = 0; k < SIZE; ++k) {
                if (D[j][k] > D[j][i] + D[i][k]) {
                    // :1->2  1->0 + 0->2
                    D[j][k] = D[j][i] + D[i][k];
                    P[j][k] = P[j][i];
                }
            }
        }
    }
    
    // D
    printf("\n-------------------------------------------------------\n");
    for (int j = 0; j < SIZE; ++j) {
        for (int k = 0; k < SIZE; ++k) {
            printf("%d\t", D[j][k]);
        }
        printf("\n");
    }
    // P
    printf("-------------------------------------------------------\n");
    for (int j = 0; j < SIZE; ++j) {
        for (int k = 0; k < SIZE; ++k) {
            printf("%d\t", P[j][k]);
        }
        printf("\n");
    }
    
    int start = 0;
    int end = 8;
    printf("v%dv%d", start, end);
    int pre = end;
    while (pre != start) {
        pre = P[pre][start];
        printf("-> %d ", pre);
    }
    printf("\n%d\n\n", D[start][end]);
}

int main(int argc, const char * argv[]) {
    printf("dijkstra:\n"); // O(n^2)v0v0
    /*
     * v0lowcost[]v0
     * lowcost[]v0vx(0)minfinals[x]1
     * vxmin + (vx-vi) < (v0-vi)lowcost[i] = min + vx-vivivx
     * 
     */
    dijkstra();
    
    printf("floyd:\n"); // O(n^3) 
    /*
     * D[x][y] = min(D[x][y], D[x][i] + D[i][y]
     * 
     * 
     * v1-2 < v1-0 + v0-2v1-2 = v1-0 + v0-2P[1][2]P[1][0] = 0
     * v2-3 < v2-1 + v1-3v2-3 = v1-0 + v0-2P[2][3]P[2][1] = 1
     * 
     */
    floyd();
    return 0;
}