【2023王道数据结构】【图】通过C++实现图的Dijkstra（迪杰斯特拉）算法求单源最短路径问题C、C++完整实现（可直接运行）

~~~笔锋至此又怎能平淡而终，故事开始便不承认普通✌✌✌

✌ 题目及题解持续更新中
【2023王道数据结构目录】课后算法设计题C、C++代码实现完整版大全

题目： 通过C++实现图的Dijkstra（迪杰斯特拉）算法求单源最短路径问题

Dijkstra（迪杰斯特拉）算法求单源最短路径问题

• 初始化源点的距离数组、访问数组、前驱结点数组
• 找到未访问且距离最小的结点，将其置为以确定最短路径
• 遍历该节点的邻居（未确定最短路径）
• 如果发现该节点到邻居的距离+源点到该点的最短距离小于源点直接到其邻居的最短距离
• 将其数组进行更新，找到最短路径
• 重复上述操作，直到全部结点确立最短路径

权值图：

Dijkstra计算结果

代码实现：

#include 
#include 
using namespace std;
#define MAX_VERTEX_NUM 100
#define VERTEXS 7
#define EDGES 7


typedef struct
{
    char vertex[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num, edge_num; // 顶点数量、边的数量
} Graph;

void InitGraph(Graph &g, char vertex[], int edge[][EDGES], int n)
{
    

    g.vertex_num = n;
    g.edge_num = 0;

    // 初始化图的顶点信息
    for (int i = 0; i < n; i++)
    {
        g.vertex[i] = vertex[i];
    }

    // 初始化图的邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && edge[i][j] == 0)
            {
                g.edge[i][j] = INT_MAX;
            }
            else
            {
                g.edge[i][j] = edge[i][j];
            }

            // 如果存在路径，将边的条数加1
            if (edge[i][j] != 0)
            {
                g.edge_num++;
            }
        }
    }
}

void PrintArray(Graph g, int array[])
{
    

    for (int i = 0; i < g.vertex_num; i++)
    {
        cout << array[i] << 't';
    }
    cout << endl;
}

void PrintGraph(Graph g)
{
    

    cout << "图的邻接矩阵:" << endl;
    for (int i = 0; i < g.vertex_num; i++)
    {
        for (int j = 0; j < g.vertex_num; j++)
        {
            if (g.edge[i][j] == INT_MAX)
            {
                cout << "∞" << 't';
            }
            else
            {
                cout << g.edge[i][j] << 't';
            }
        }
        cout << endl;
    }
}

void PrintPath(int v, int target, int path[])
{
    

    stack s; // 初始化一个栈保存路径信息
    int i = target;

    // 不断找到其前驱结点
    while (i != -1)
    {
        s.push(i);
        i = path[i];
    }

    cout << "顶点" << v << "到顶点" << target << "最短路径为:";
    while (!s.empty())
    {
        if (s.top() == target)
        {
            cout << s.top();
        }
        else
        {
            cout << s.top() << " -> ";
        }
        s.pop();
    }
    cout << endl;
}

void PrintAllPath(Graph g, int v, int path[])
{
    

    int i = 0;

    // 只要不是自身，就去打印最短路径
    for (int i = 0; i < g.vertex_num; i++)
    {
        int target = stoi(string(1, g.vertex[i]));
        if (v == target)
        {
            continue;
        }

        PrintPath(v, target, path);
    }
}

void SedgeToVertexAndEdge(string s_edge[], int edge[][EDGES])
{
    

    for (int k = 1; k <= stoi(s_edge[0]); k++)
    {
        edge[stoi(string(1, s_edge[k][0]))][stoi(string(1, s_edge[k][2]))] = stoi(string(1, s_edge[k][4]));
    }
}

void InitGraph(Graph &g)
{
    

    char vertex[] = {'0', '1', '2', '3', '4', '5', '6'}; // 图的顶点名称
    // 图的邻接矩阵
    int edge[EDGES][EDGES];

    // 图的权值边
    string s_edge[] = {"12",
                       "0-1-4",
                       "0-3-6",
                       "0-2-6",
                       "1-2-1",
                       "1-4-7",
                       "2-5-4",
                       "2-4-6",
                       "3-2-2",
                       "3-5-5",
                       "4-6-6",
                       "5-4-1",
                       "5-6-8"};

    // 将权值边转化成邻接矩阵
    SedgeToVertexAndEdge(s_edge, edge);
    // 初始化图结构
    InitGraph(g, vertex, edge, VERTEXS);
}

int FindDistanceMinPos(Graph g, int distance[], bool visited[])
{
    

    int dis_min = INT_MAX; // 保存最小值
    int dis_pos = -1;      // 保存对应最小值的下标

    for (int i = 0; i < g.vertex_num; i++)
    {
        // 如果还未确定最短路径，同时小于当前最小距离值，修改
        if (!visited[i] && distance[i] < dis_min)
        {
            dis_min = distance[i];
            dis_pos = i;
        }
    }

    return dis_pos;
}

void Dijkstra(Graph g, int distance[], int path[], bool visited[], int v)
{
    

    int round = 1; // 处理的轮数，应为n-1轮
    // 初始化数组，将源点置为已确定最短路径
    visited[v] = true;
    // 更新源点的距离矩阵
    distance[v] = 0;
    for (int i = 0; i < g.vertex_num; i++)
    {
        // 将distance更新为v的邻接点的权值，且将路径指向v
        if (g.edge[v][i] != 0 && g.edge[v][i] != INT_MAX)
        {
            distance[i] = g.edge[v][i];
            path[i] = v;
        }
    }

    // 处理n-1轮
    while (round++ < g.vertex_num)
    {
        // 找到未确定最短路径且距离最小点的下标
        int min_pos = FindDistanceMinPos(g, distance, visited);

        // 将其置为true，表明该点已经确定，利用贪心策略
        visited[min_pos] = true;

        // 遍历其临界点，如果发现 g.edge[min_pos][i] + distance[min_pos] < distance[i]，则将距离矩阵更细，找到更短的路径
        for (int i = 0; i < g.vertex_num; i++)
        {
            if (g.edge[min_pos][i] != 0 && g.edge[min_pos][i] != INT_MAX && !visited[i])
            {
                if (g.edge[min_pos][i] + distance[min_pos] < distance[i])
                {
                    distance[i] = g.edge[min_pos][i] + distance[min_pos];
                    path[i] = min_pos;
                }
            }
        }
    }
}

int main()
{
    // 初始化图结构
    Graph g;
    InitGraph(g);

    PrintGraph(g);
    cout << "顶点数:" << g.vertex_num << 't' << "边数:" << g.edge_num << endl;

    // 初始化矩阵
    bool visited[g.vertex_num] = {false};
    int distance[g.vertex_num];
    int path[g.vertex_num];

    // 将距离矩阵填充为最大值
    fill(distance, distance + g.vertex_num, INT_MAX);
    // 路径初始值赋为-1
    fill(path, path + g.vertex_num, -1);

    // 调用Dijkstra算法
    Dijkstra(g, distance, path, visited, 0);
    cout << "distance数组:" << endl;
    PrintArray(g, distance);
    cout << "path数组:" << endl;
    PrintArray(g, path);
    cout << "最短路径:" << endl;
    PrintAllPath(g, 0, path);
}