//Dijkstra算法
void GraphData::ShortPath_Dijkstra(GraphArray *pArray)
{
    //Dijkstra算法和最小生成树的算法，在某种程度是相似的
    int min,i,j,k;
    int nNodeIndex[MAXVEX];      //保存相关顶点坐标，1就是已经遍历访问的过结点(在最小生成树中为数值表示遍历过同时值与坐标是一条边）
    int nNodeWeight[MAXVEX];     //保存某个顶点到各个顶点的权值，为不为0和最大值表示遍历过了。
    int nPathLength[MAXVEX];     //坐标和元素表示为同时值和坐标表示一边，与Primes有相同的
    //两个数组的初始化
    printf("开始初始化，当前顶点边的权值为：");
    for(i = 0;i<pArray->numVertexes;i++)
    {
        nNodeIndex[i] = 0; 
        nNodeWeight[i] = pArray->arg[0][i];//设定在矩阵中第一个顶点为初始点。
        nPathLength[i] = 0;
        printf(" %c",nNodeWeight[i]);
    }
    nNodeWeight[0] = 0;  //选取坐标点0为起始点。
    nNodeIndex[0] = 1;  //这样0就是起始点，设为1.（和Prime的不同）
    //算法思想
    for (i = 1;i< pArray->numVertexes;i++)
    {
        min = INFINITY;    //初始化权值为最大值;
        j = 1;
        k = 0;
        // 循环全部顶点，寻找与初始点边权值最小的顶点，记下权值和坐标
        while(j < pArray->numVertexes)
        {
            //如果权值不为0,且权值小于min,为0表示本身
            if (!nNodeIndex[j]&&nNodeWeight[j] < min)  //这里Prime是权重中不为0,
            {
                min     = nNodeWeight[j];
                k = j;     //保存上述顶点的坐标值
            }
            j++;
        }
        printf("当前顶点边中权值最小边(%d,%d)
",nNodeIndex[k] , k); //打印当前顶点边中权值最小
        //nNodeWeight[k] = 0; //将当前顶点的权值设置为0，表示此顶点已经完成任务
        nNodeIndex[k] = 1;     //将目前找到的最近的顶点置为1

        //for (j = 1;j< pArray->numVertexes;j++)  //循环所有顶点，查找与k顶点的最小边
        //{
        //    //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
        //    if (nNodeWeight[j] != 0&&pArray->arg[k][j] < nNodeWeight[j])
        //    {
        //        nNodeWeight[j] = pArray->arg[k][j];
        //        nNodeIndex[j] = k;     //将下标为k的顶点存入adjvex
        //    }
        //}
        //修正当前最短路径及距离
        for (j = 1;j< pArray->numVertexes;j++)  //循环所有顶点，查找与k顶点的最小边
        {
            //若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
            if (!nNodeIndex[j] && pArray->arg[k][j] + min< nNodeWeight[j])
            {
                nNodeWeight[j] = pArray->arg[k][j] + min;
                nPathLength[j] = k;     //将下标为k的顶点存入adjvex
            }
        }
        //打印当前顶点状况
        printf("坐标点数组为：");
        for(j = 0;j< pArray->numVertexes;j++)
        {
            printf("%3d ",nPathLength[j]);
        }
        printf("
");
        printf("权重数组为：");
        for(j = 0;j< pArray->numVertexes;j++)
        {
            printf("%3d ",nNodeWeight[j]);
        }
        printf("
");
    }

}

//Floyd算法
void GraphData::ShortPath_Floyd(GraphArray *pArray)
{
    int i,j,m,k;
    int nNodeIndex[MAXVEX][MAXVEX];
    int nNodeWeight[MAXVEX][MAXVEX];
    
    for ( i = 0;i< pArray->numVertexes;i++)
    {
        for (j = 0;j< pArray->numVertexes;j++)
        { 
            nNodeIndex[i][j] = j;                         /* 初始化 */
            nNodeWeight[i][j] = pArray->arg[i][j];  /* [i][j]值即为对应点间的权值 */
        }
    }
    for (i = 0;i< pArray->numVertexes;i++)
    {
        for (j = 0;j< pArray->numVertexes;j++)
        {
            for (k = 0;k<pArray->numVertexes;k++)
            {
                if (pArray->arg[j][k] > pArray->arg[j][i] + pArray->arg[i][k])
                {
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    nNodeWeight[j][k] = pArray->arg[j][i] + pArray->arg[i][k];  /* 将当前两点间权值设为更小的一个 */
                    nNodeIndex[j][k] = nNodeIndex[j][i];  /* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
    for (i = 0; i< pArray->numVertexes;i++)
    {
        for (j = 0;j< pArray->numVertexes;j++)
        {
            printf("v%d-v%d weight: %d",i,j,nNodeWeight[i][j]);
                m = nNodeIndex[i][j];    //获得第一个路径点的顶点下标
            printf("path :%d",i);    //打印源点
            while(m!=j)
            {
                printf(" -> %d",m);   //打印路径顶点
                m = nNodeIndex[m][j];   //获取下一个路径顶点下标
            }
            printf(" -> %d
",m);    //打印路径终点。
        }

        printf("
");
    }
}