图的最短路径之Dijkstra算法C/C++代码实现-蒲公英云

图的最短路径之Dijkstra算法C/C++代码实现

迪杰斯特拉Dijkstra算法：

该算法用来求解从某个源点到其余各顶点的最短路径

以该图为例：
在这里插入图片描述
其邻接矩阵为：

最短路径为：

具体过程：

算法中用到了三个辅组数组：
S[i]：布尔值记录到顶点最短路径是否已经被确定
Path[i]:记录顶点最短路径的直接前驱顶点序号
D[i]:记录最短路径的长度，初值为权值
在这里插入图片描述
（上表中的i表示循环次数）

每次从D数组中选择最小的加入到S集合，紧接着用刚加入的顶点和个顶点比较如果路径变小了则更新相应D数组

代码如下：

#include<stdio.h>
#define MaxInt 999            //定义无穷大
#define MVNum 100
typedef char VerTexType;    //顶点类型
typedef int ArcType;        //边权值类型
//邻接矩阵存储结构
typedef struct
{
    VerTexType vexs[MVNum];                //顶点表
    ArcType arcs[MVNum][MVNum];            //邻接矩阵
    int vexnum, arcnum;                    //图的当前点数和边数
}AMGraph;
void printGraph(AMGraph G);
int LocateVex(AMGraph G, char v);
//创建有向网
void CreateUDN(AMGraph &G)
{
    G.vexnum = 6;                        //输入总顶点数和边数
    G.arcnum = 8;
    G.vexs[0] = 'v0';                    //输入顶点信息
    G.vexs[1] = 'v1';
    G.vexs[2] = 'v2';
    G.vexs[3] = 'v3';
    G.vexs[4] = 'v4';
    G.vexs[5] = 'v5';
    for (int i = 0; i < G.vexnum; i++)            //初始化邻接矩阵为极大值
    {
        for (int j = 0; j < G.vexnum; j++)
        {
            G.arcs[i][j] = MaxInt;
        }
    }
    //输入权值
    int i, j;
    i = LocateVex(G, 'v0');
    j = LocateVex(G, 'v2');
    G.arcs[i][j] = 10;
    i = LocateVex(G, 'v0');
    j = LocateVex(G, 'v4');
    G.arcs[i][j] = 30;
    i = LocateVex(G, 'v0');
    j = LocateVex(G, 'v5');
    G.arcs[i][j] = 100;
    i = LocateVex(G, 'v1');
    j = LocateVex(G, 'v2');
    G.arcs[i][j] = 5;
    i = LocateVex(G, 'v2');
    j = LocateVex(G, 'v3');
    G.arcs[i][j] = 50;
    i = LocateVex(G, 'v3');
    j = LocateVex(G, 'v5');
    G.arcs[i][j] = 10;
    i = LocateVex(G, 'v4');
    j = LocateVex(G, 'v3');
    G.arcs[i][j] = 20;
    i = LocateVex(G, 'v4');
    j = LocateVex(G, 'v5');
    G.arcs[i][j] = 60;
    printGraph(G);
}
//返回顶点在数组中的下标
int LocateVex(AMGraph G, char v)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.vexs[i] == v)
        {
            return i;
        }
    }
}
//打印输出邻接矩阵
void printGraph(AMGraph G)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        printf("v%d :", i + 1);
        for (int j = 0; j < G.vexnum; j++)
        {
            printf("%5d ", G.arcs[i][j]);
        }
        printf("\n");
    }
}
//邻接矩阵深度优先遍历
bool visited[MVNum];
void DFS_AM(AMGraph G, int v)
{
    printf("v%c->", G.vexs[v]);
    visited[v] = true;
    for (int w = 0; w < G.vexnum; w++)
    {
        if ((G.arcs[v][w]) != 0 && (!visited[w]))
        {
            DFS_AM(G, w);
        }
    }
}
//最短路径迪杰斯特拉算法
bool S[MVNum];                //判断v0到vi是否已经被确定最短路径长度
int D[MVNum];                //存放v0到vi的最短路径长度值
int Path[MVNum];            //存放vi的直接前驱顶点序号
void ShortestPath_DIJ(AMGraph G, int v0)
{
    //初始化
    int n = G.vexnum;        //图的顶点数
    for (int v = 0; v< n; v++)
    {
        S[v] = false;
        D[v] = G.arcs[v0][v];
        if (D[v]<MaxInt)    //如果v0到v有路径，则Path数组置为v0
        {
            Path[v] = v0;
        }
        else {
                    //否则置为-1
            Path[v] = -1;
        }
    }
    S[v0] = true;
    D[v0] = 0;
    //算法开始
    for (int i = 1; i < n; i++)
    {
        int min = MaxInt;
        int v = 0;
        //查找D[]中权值最小的且加入到完成集合S
        for (int w = 0; w <n; w++)
        {
            if (!S[w] && D[w] < min)
            {
                v = w;            //最小的序号存入v中
                min = D[w];        //最小权值存入min
            }
        }
        S[v] = true;
        //完成集合S添加新顶点后更新最短路径信息
        for (int w = 0; w < n; w++)
        {
            if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
            {
                D[w] = D[v] + G.arcs[v][w];
                Path[w] = v;
            }
        }
        //逆序输出最短路径
        int t = v;
        while (Path[t] != -1)
        {
            printf("v%c<— ", G.vexs[t]);
            t = Path[t];
        }
        printf("v0\n");
    }
}
int main()
{
    AMGraph G;
    CreateUDN(G);
    int v = 0;
    printf("深度优先遍历：：");
    DFS_AM(G, v);
    int v0 = 0;
    printf("\n====================================\n");
    printf("v0到各顶点的最短路径：\n");
    ShortestPath_DIJ(G, v0);
}