class MatrixUDG {

    #define MAX    100

    #define INF    (~(0x1<<31))        // 无穷大(即0X7FFFFFFF)

    private:

        char mVexs[MAX];    // 顶点集合

        int mVexNum;             // 顶点数

        int mEdgNum;             // 边数

        int mMatrix[MAX][MAX];   // 邻接矩阵

    public:

        // 创建图(自己输入数据)

        MatrixUDG();

        // 创建图(用已提供的矩阵)

        //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);

        MatrixUDG(char vexs[], int vlen, int matrix[][9]);

        ~MatrixUDG();

        // 深度优先搜索遍历图

        void DFS();

        // 广度优先搜索（类似于树的层次遍历）

        void BFS();

        // prim最小生成树(从start开始生成最小生成树)

        void prim(int start);

        // 克鲁斯卡尔（Kruskal)最小生成树

        void kruskal();

        // Dijkstra最短路径

        void dijkstra(int vs, int vexs[], int dist[]);

        // 打印矩阵队列图

        void print();

    private:

        // 读取一个输入字符

        char readChar();

        // 返回ch在mMatrix矩阵中的位置

        int getPosition(char ch);

        // 返回顶点v的第一个邻接顶点的索引，失败则返回-1

        int firstVertex(int v);

        // 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1

        int nextVertex(int v, int w);

        // 深度优先搜索遍历图的递归实现

        void DFS(int i, int *visited);

        // 获取图中的边

        EData* getEdges();

        // 对边按照权值大小进行排序(由小到大)

        void sortEdges(EData* edges, int elen);

        // 获取i的终点

        int getEnd(int vends[], int i);

};

/*

 * Dijkstra最短路径。

 * 即，统计图中"顶点vs"到其它各个顶点的最短路径。

 *

 * 参数说明：

 *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。

 *     prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。

 *     dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。

 */

void MatrixUDG::dijkstra(int vs, int prev[], int dist[])

{

    int i,j,k;

    int min;

    int tmp;

    int flag[MAX];      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。

    // 初始化

    for (i = 0; i < mVexNum; i++)

    {

        flag[i] = 0;              // 顶点i的最短路径还没获取到。

        prev[i] = 0;              // 顶点i的前驱顶点为0。

        dist[i] = mMatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。

    }

    // 对"顶点vs"自身进行初始化

    flag[vs] = 1;

    dist[vs] = 0;

    // 遍历mVexNum-1次；每次找出一个顶点的最短路径。

    for (i = 1; i < mVexNum; i++)

    {

        // 寻找当前最小的路径；

        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。

        min = INF;

        for (j = 0; j < mVexNum; j++)

        {

            if (flag[j]==0 && dist[j]<min)

            {

                min = dist[j];

                k = j;

            }

        }

        // 标记"顶点k"为已经获取到最短路径

        flag[k] = 1;

        // 修正当前最短路径和前驱顶点

        // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。

        for (j = 0; j < mVexNum; j++)

        {

            tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));

            if (flag[j] == 0 && (tmp  < dist[j]) )

            {

                dist[j] = tmp;

                prev[j] = k;

            }

        }

    }

    // 打印dijkstra最短路径的结果

    cout << "dijkstra(" << mVexs[vs] << "): " << endl;

    for (i = 0; i < mVexNum; i++)

        cout << "  shortest(" << mVexs[vs] << ", " << mVexs[i] << ")=" << dist[i] << endl;

}