图的最短路问题

最短路问题 —— 若网络中的每条边都有一个数值（长度、成本、时间等），找出两节点之间总权和最小的路径

数据结构课代码实现 之 最短路问题

简要理解

Dijkstra算法：一个顶点到其余各顶点的最短路算法

Floyd算法：求多源汇最短路

Dijkstra算法

主要思想为维护一个 dist数组 保存起点到其余各点的最短路长度

初始化时将 dist数组中每个 dist[j] 初始化为起点到 j点的边长 （无边则初始化为INFINITY）

之后每次选择 dist数组 中最小的元素 将其对应点设置为已确定最短路径

并用其更新其余所有未确定最短路径的点的最短路长度

n - 1 次操作后即可更新所有点的最短路

Floyd算法

用中转点 k 更新 点 i 到 点 j 的最短路径

d[i][j] = d[i][k] + d[k][j]

代码实现

用邻接矩阵存图

Dijkstra算法

typedef struct ArcNode
{
    struct ArcNode* next;
    int vex;
}ArcNode;

struct Path
{
    ArcNode* first;             // 用单链表保存起点到每个节点的路径
    int num;
}path[MAX_VERTEX_NUM];

bool final[MAX_VERTEX_NUM];    // final数组 记录每个点的最短路是否被确定

void dijkstra(MGraph &G, int v0, Path* p, int d[])
{
    for(int i = 0;i < G.vexnum;i++)
    {
        final[i] = false;
        p[i].num = 1;
        p[i].first = (ArcNode *)malloc(sizeof(ArcNode));
        p[i].first->vex = v0;
        d[i] = G.arcs[v0][i].adj;
        if(d[i] < INFINITY)
        {
            p[i].first->next = (ArcNode *)malloc(sizeof(ArcNode));
            p[i].first->next->vex = i;
            p[i].num = 2;          // 初始化路径
        }
    }
    
    int poi;

    for(int i = 1;i < G.vexnum;i++)
    {
        int min = INFINITY;
        for(int j = 0;j < G.vexnum;j++)
        {
            if(!final[j])
            {
                if(d[j] < min)
                {
                    poi = j;
                    min = d[j];       // 每次在所有点中选择距离起点最近的点
                }   
            }
        }

        final[poi] = true;            // 记录此点已确定最短路

        for(int j = 0;j < G.vexnum;j++)
        {
            // 用已确定最短路的点更新其余所有未确定最短路的点的 dist
            if(!final[j] && (min + G.arcs[poi][j].adj < d[j]))
            {
                d[j] = min + G.arcs[poi][j].adj;     
                
                ArcNode* clean = p[j].first;

                for(int i = 0;i < path[j].num;i++)
                {
                    ArcNode* last = clean;
                    clean = clean->next;
                    free(last);                    // 删除 j点 原路径
                }           

                p[j].first = (ArcNode *)malloc(sizeof(ArcNode));

                ArcNode* tep = p[j].first;
                ArcNode* tmp = p[poi].first;        // 更新 起点到j点 的最短路径记录

                for(int k = 0;k < p[poi].num;k++, tep = tep->next, tmp = tmp->next)
                {
                    tep->vex = tmp->vex;
                    tep->next = (ArcNode *)malloc(sizeof(ArcNode));
                }

                p[j].num = p[poi].num;
                tep->vex = j;
                p[j].num++;
            }
        }
    }
}

int main()
{
    MGraph a;
    CreateGraph(a);
    int d[a.vexnum];       // 维护一个 dist数组储存起点到其余各点的最短路径
    dijkstra(a, 0, path, d);

    int x, y;
    cout << "请输入起点与要查询的点(输入点的储存值)：";
    cin >> x >> y;
    
    x = LocateVex(a, x);
    y = LocateVex(a, y);

    cout << x << "号结点到" << y << "号结点的最短路长度为：";
    cout << d[y] << endl;

    cout << x << "号结点到" << y << "号结点的最短路路径长度为：";
    cout << path[y].num << endl;

    ArcNode* j = path[y].first;
    cout << "记录的路径为：" << endl;
    for(int i = 0;i < path[y].num;i++, j = j->next)
    {
        cout << j->vex << endl;
    }
    return 0;
}

Floyd算法

typedef struct ArcNode
{
    struct ArcNode* next;
    int vex;
}ArcNode;

struct Path
{
    ArcNode* first;
    int num;
}**path;          // 单链表储存一点到另一点最短路径

void Floyd(MGraph &G, Path** p, int** d)
{
    for(int i = 0;i < G.vexnum;i++)
    {
        for(int j = 0;j < G.vexnum;j++)
        {
            p[i][j].num = 1;
            p[i][j].first = (ArcNode *)malloc(sizeof(ArcNode));
            p[i][j].first->vex = i;
            d[i][j] = G.arcs[i][j].adj;
            if(d[i][j] < INFINITY)
            {
                p[i][j].first->next = (ArcNode *)malloc(sizeof(ArcNode));
                p[i][j].first->next->vex = j;
                p[i][j].num = 2;
            }                           // 初始化路径
        }
    }
    
    for(int i = 0;i < G.vexnum;i++)
    {
        for(int j = 0;j < G.vexnum;j++)
        {
            for(int k = 0;k < G.vexnum;k++)
            {
                if(d[i][k] + d[k][j] < d[i][j])    
                {
                    d[i][j] = d[i][k] + d[k][j];      // 满足条件 更新最短路径

                    ArcNode* clean = p[i][j].first;

                    for(int u = 0;u < path[i][j].num;u++)
                    {
                        ArcNode* last = clean;
                        clean = clean->next;
                        free(last);                    // 删除 i 到 j 点的原路径
                    }

                    p[i][j].first = (ArcNode *)malloc(sizeof(ArcNode));

                    ArcNode* tep = p[i][j].first;
                    ArcNode* tmp = p[i][k].first;

                    for(int u = 0;u < p[i][k].num;u++, tep = tep->next, tmp = tmp->next)
                    {
                        tep->vex = tmp->vex;
                        tep->next = (ArcNode *)malloc(sizeof(ArcNode));
                    }

                    tmp = p[k][j].first->next; // i 到 k 的路径的最后一个点 与 k 到 j 的路径的第一个点是重复的，删除其一
                    for(int u = 0;u < p[k][j].num - 1;u++, tep = tep->next, tmp = tmp->next)
                    {
                        tep->vex = tmp->vex;
                        tep->next = (ArcNode *)malloc(sizeof(ArcNode));
                    }

                    p[i][j].num = p[i][k].num + p[k][j].num - 1;  // i 到 k 的路径的最后一个点 与 k 到 j 的路径的第一个点是重复的，长度减一
                }
            }
        }
    }
}

int main()
{
    MGraph a;
    CreateGraph(a);
    int** d;
    path = (Path**)malloc(a.vexnum * sizeof(Path*));
    for(int i = 0;i < a.vexnum;i++)
        path[i] = (Path*)malloc(a.vexnum * sizeof(Path));

    d = (int**)malloc(a.vexnum * sizeof(int*));
    for(int i = 0;i < a.vexnum;i++)
        d[i] = (int*)malloc(a.vexnum * sizeof(int));
    Floyd(a, path, d);

    int x, y;
    cout << "请输入查询的起点与终点(输入点的储存值)：";
    cin >> x >> y;

    x = LocateVex(a, x);
    y = LocateVex(a, y);

    cout << x << "号结点到" << y << "号结点的最短路长度为：";
    cout << d[x][y] << endl;

    cout << x << "号结点到" << y << "号结点的最短路路径长度为：";
    cout << path[x][y].num << endl;

    ArcNode* tep = path[x][y].first;
    cout << "记录的路径为：" << endl;
    for(int u = 0;u < path[x][y].num;u++, tep = tep->next)
        cout << tep->vex << endl;
    return 0;
}