/*
* File:        longest.c
* Desciption:  動態規劃算法計算網絡的最長路線和最短路線
* Created:    2001/12/2
* Author:      Justin Hou [mailto:justin_hou@hotmail.com]
*
*/
#include <stdio.h>
#define  N  7                                              /* 頂點數目    */
#define  I  999                                            /* 表示無窮大  */

int graph[N][N] = {                                        /* 圖的鄰接矩陣 */
        {I, 4, 5, 8, I, I, I},
        {I, I, I, 6, 6, I, I},
        {I, I, I, 5, I, 7, I},
        {I, I, I, I, 8, 9, 9},
        {I, I, I, I, I, I, 5},
        {I, I, I, I, I, I, 4},
        {I, I, I, I, I, I, I}
};
int List[N];                                                /* 存放拓撲序列 */

int TopologicalOrder();                                    /* 拓撲排序函數 */

void main()                                                /* 主 函 數    */
{
        int i, j, k, l;
        int ee[N], el[N];                                  /* 最長最短距離 */
        int path_e[N][N], path_l[N][N], n_e[N], n_l[N];    /* 記錄路徑數據 */

        /* 初始化數據 */
        for (i = 0; i < N; i++) {
                n_e[i] = 0;                      /* 到 i 的最短路線的結點數 */
                n_l[i] = 0;                      /* 到 i 的最長路線的結點數 */
                ee[i] = I;
                el[i] = 0;
        }
        ee[0] = el[0] = 0;                                  /* 初始化頭結點 */
        path_e[0][0] = 0;
        path_l[0][0] = 0;
        n_e[0] = 1;
        n_l[0] = 1;

        /* 拓撲排序 */
        if (!TopologicalOrder())
                return;

        /* 對于拓撲序列,運用動態規劃步步算出最長路線與最短路線 */
        for (i = 0; i < N; i++) {

                /* 提取拓撲序列的元素 */
                k = List[i];
                /* 更新它所指向頂點的所有數據 */
                for (j = 0; j < N; j++) {

                        /* 尋找指向的頂點 */
                        if (graph[k][j] != I) {

                                /* 如果新路徑更短 */
                                if (graph[k][j] + ee[k] < ee[j]) {

                                        /* 更新最短路徑長度 */
                                        ee[j] = graph[k][j] + ee[k];
                                        /* 更新最短路線 */
                                        for (l = 0; l < n_e[k]; l++) {
                                                path_e[j][l] = path_e[k][l];
                                        }
                                        path_e[j][l] = j;
                                        n_e[j] = l + 1;
                                }

                                /* 如果新路徑更長 */
                                if (graph[k][j] + el[k] > el[j]) {

                                        /* 更新最長路徑長度 */
                                        el[j] = graph[k][j] + el[k];
                                        /* 更新最長路線 */
                                        for (l = 0; l < n_l[k]; l++) {
                                                path_l[j][l] = path_l[k][l];
                                        }
                                        path_l[j][l] = j;
                                        n_l[j] = l + 1;
                                }
                        }
                }
        }

        /* 輸出結果到屏幕 */
        for (i = 0; i < N; i++) {
                printf("shortest(%d): %2d    Path: ", i + 1, ee[i]);
                for (j = 0; j < n_e[i]; j++) {
                        printf("%d ", path_e[i][j] + 1);
                }
                printf("\n");        
                printf("longest (%d): %2d    Path: ", i + 1, el[i]);
                for (j = 0; j < n_l[i]; j++) {
                        printf("%d ", path_l[i][j] + 1);
                }
                printf("\n");
        }
}

int TopologicalOrder()
{
        int i, j, top, count;
        int indegree[N], Stack[N];

        top = 0;                                            /* 棧頂標志    */
        for (i = 0; i < N; i++) {
                indegree[i] = 0;                            /* 初始化入度  */
                for (j = 0; j < N; j++) {
                        if (graph[j][i] != I) {            /* 如連通      */
                                indegree[i]++;              /* 入度自增1    */
                        }
                }
                if (!indegree[i]){                          /* 如入度為零  */
                        Stack[top++] = i;                  /* 入棧        */
                }
        }
        count = 0;                                          /* 輸出頂點數  */
        while (top != 0) {
                i = Stack[--top];
                List[count++] = i;
                for (j = 0; j < N; j++) {
                        if (graph[i][j] != I) {            /* 如連通      */
                                if (!(--indegree[j])) {    /* 而且入度為零 */
                                        Stack[top++] = j;  /* 入棧        */
                                }
                        }
                }/* for */
        }/* while */

        return (count < N) ? 0 : 1;
}