使用c++,根据邻接矩阵实现Dijkstra算法

Dijkstra算法是一种用于求解单源最短路径的贪心算法，可以在带权有向图或无向图中使用。下面是使用C++语言实现Dijkstra算法的代码，基于邻接矩阵存储图。

#include <iostream>
#include <limits.h>  // 定义INT_MAX
using namespace std;

// 定义邻接矩阵存储图的类
class Graph {
private:
    int** adjMatrix;  // 邻接矩阵
    int vertexNum;    // 顶点数
public:
    Graph(int num);  // 构造函数
    ~Graph();        // 析构函数
    void addEdge(int src, int dst, int weight);  // 添加边
    void dijkstra(int src);                      // Dijkstra算法
};

Graph::Graph(int num) {
    // 初始化邻接矩阵
    vertexNum = num;
    adjMatrix = new int*[vertexNum];
    for (int i = 0; i < vertexNum; ++i) {
        adjMatrix[i] = new int[vertexNum];
        for (int j = 0; j < vertexNum; ++j) {
            adjMatrix[i][j] = 0;
        }
    }
}

Graph::~Graph() {
    // 释放内存
    for (int i = 0; i < vertexNum; ++i) {
        delete[] adjMatrix[i];
    }
    delete[] adjMatrix;
}

void Graph::addEdge(int src, int dst, int weight) {
    // 添加边
    adjMatrix[src][dst] = weight;
    adjMatrix[dst][src] = weight;
}

void Graph::dijkstra(int src) {
    int dist[vertexNum];    // 存储最短距离
    bool visited[vertexNum];  // 标记顶点是否已访问

    // 初始化
    for (int i = 0; i < vertexNum; ++i) {
        dist[i] = INT_MAX;     // 初始距离设为无穷大
        visited[i] = false;    // 初始标记都未访问
    }
    dist[src] = 0;              // 起点到自己的距离为0

    // 迭代vertexNum-1次
    for (int i = 0; i < vertexNum-1; ++i) {
        // 找到当前未访问顶点中距离最小的顶点
        int minDist = INT_MAX;
        int minIndex = 0;
        for (int j = 0; j < vertexNum; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        // 标记该顶点为已访问
        visited[minIndex] = true;

        // 更新与该顶点相邻的顶点的最短距离
        for (int k = 0; k < vertexNum; ++k) {
            if (!visited[k] && adjMatrix[minIndex][k] > 0 && 
                dist[minIndex] + adjMatrix[minIndex][k] < dist[k]) {
                dist[k] = dist[minIndex] + adjMatrix[minIndex][k];
            }
        }
    }

    // 输出最短距离
    cout << "Vertex\tDistance from Source" << endl;
    for (int i = 0; i < vertexNum; ++i) {
        cout << i << "\t" << dist[i] << endl;
    }
}

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 4, 4);
    g.addEdge(3, 1, 3);
    g.addEdge(3, 2, 9);
    g.addEdge(3, 4, 2);
    g.addEdge(4, 0, 7);
    g.addEdge(4, 2, 6);
    g.dijkstra(0);
    return 0;
}

上述代码中，我们首先定义了一个邻接矩阵存储图的类 Graph，并在其中实现了添加边和Dijkstra算法两个函数。在主函数中，我们创建了一个包含5个顶点的图，并添加了10条边，然后调用了Dijkstra算法求最短路径。运行结果如下：

Vertex	Distance from Source
0	0
1	8
2	9
3	5
4	7

表示从顶点0出发到其他各个顶点的最短距离。