最短路径算法，Dijkstra与Floyd算法的实现

- BFS算法的推广

- 通过栈对path[]进行操作，输出路径

- O(V+N)

void Unweighted(LGraph Graph, int dist[], int path[], Vertex S)
{
    //dist[]和path[]全部初始化为-1
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
    Q = CreateQueue(Graph->Nv); //创建空队列,MaxSize为外部定义的常数
    dist[S] = 0; // 初始化源点
    AddQ (Q, S);

    while(!IsEmpty(Q)) {
        V = DeleteQ(Q);
        for (W = Graph->G[V].FirstEdge; W; W = W->Next) //对V的每个邻接点W->AdjV(访问边)
            if ( dist[W->AdjV]==-1 ) { //若W->AdjV未被访问过
                dist[W->AdjV] = dist[V]+1; //W->AdjV到S的距离更新
                path[W->AdjV] = V; //将V记录在S到W->AdjV的路径上
                AddQ(Q, W->AdjV);
            }
    }
}

Vertex FindMinDist(MGraph Graph, int dist[], int collected[])
{
    Vertex MinV, V;
    int MinDist = INFINITY;
    for (V = 0; V < Graph->Nv; V++) {
        if (collected[V] == false && dist[V] < MinDist) { //若V未被收录，且dist[V]更小
            MinDist = dist[V]; //更新最小距离
            MinV = V; //更新对应顶点
        }
    }
    if (MinDist < INFINITY) //若找到最小dist
        return MinV; //返回对应的顶点下标
    else
        return ERROR;  //若这样的顶点不存在，返回错误标记
}

bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S)
{
    int collected[MaxVertexNum];
    Vertex V, W;
    for(V = 0; V < Graph->Nv; V++) {
        dist[V] = Graph->G[S][V]; //初始化和源点的距离，如果不联通则设为INFINITY
        if (dist[V] < INFINITY) //如果和源点联通
            path[V] = S;
        else //如果和源点不联通
            path[V] = -1;
        collected[V] = false;
    }
    //先将源点收入集合
    dist[S] = 0;
    collected[S] = true;

    while(1) {
        V = FindMinDist(Graph, dist, collected); //V为未被收录顶点中dist最小者
        if(V == ERROR) //若这样的V不存在
            break;
        collected[V] = true; //收录V
        for(W = 0; W < Graph->Nv; W++) //对图中的每个顶点W
            if (Graph->G[V][W] < INFINITY && collected[W] == false ) { //若W是V的邻接点并且未被收录
                if (Graph->G[V][W] < 0) //若有负边
                    return false; //不能正确解决，返回错误标记
                if (dist[V] + Graph->G[V][W] < dist[W]) { //若收录V使得dist[W]变小
                    dist[W] = dist[V] + Graph->G[V][W]; //更新dist[W]
                    path[W] = V; //更新S到W的路径
                }
            }
    }
    return true;
}

稀疏图：调用v次单源最短路径算法

- O(​​​​​​​)

- 递归操作path[i][j]可以得到路径

void Floyd(MGraph Graph, WeightType D[] [MaxVertexNum], Vertex path[][MaxVertexNum])
{
    Vertex i, j, k;
    for (i = 0; i < Graph->Nv; i++)
        for(j = 0; j Nv; j++) {
            D[i][j] = Graph->G[i][j]; //初始化最短路径矩阵
            path[i][j] = -1;
        }
    for(k = 0; k < Graph->Nv; k++)
        for(i = 0; i < Graph->Nv; i++)
            for(j = 0; j < Graph->Nv; j++)
                if(D[i][k] + D[k][j] < D[i][j]) { //如果经过k的路径更短
                    D[i][j] = D[i][k] + D[k][j]; //更新最短路径长度
                    path[i][j] = k;
                }
    return;
}

bool Floyd(LGraph Graph, int x, int y)
{
    Vertex i, j, k; //初始化
    LengthType D[MaxVertexNum][MaxVertexNum];
    Vertex path[MaxVertexNum][MaxVertexNum];
    
    for (i = 0; i < Graph->Nv; i++)
        for(j = 0; j < Graph->Nv; j++) {
            if(i==j) D[i][j]=0;
            else D[i][j]=INFINITY;
            path[i][j] = -1;
        }
    for(i = 0; i < Graph->Nv; i++) {
        PAdjVNode e = Graph->G[i].FirstEdge;
        while(e) {
            D[i][e->AdjV] = e->length;
            e = e->Next;
        }
    }
    for(i = 0; k < Graph->Nv; k++)
        for(i = 0; i < Graph->Nv; i++)
            for(j = 0; j < Graph->Nv; j++)
                if(D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    if (i == j && D[i][j]<0) //若发现负值圈
                        return false; //不能正确解决，返回错误标记
                    path[i][j] = k;
                }
    return true;
}