利用dijkstra算法使用c++实现求解点对间最小距离

好的，让我来回答你的问题。Dijkstra算法是一种用于求解最短路径的算法，它可以在加权图中查找从一个节点到所有其他节点的最短路径。你可以使用C语言实现Dijkstra算法，主要步骤包括构建有向图的邻接矩阵、定义距离向量和前驱向量、初始化距离向量和前驱向量、循环更新距离向量和前驱向量、最后输出最短路径和最小距离。希望能帮到你！

相关问题

使用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出发到其他各个顶点的最短距离。

C++实现Dijkstra算法

Dijkstra算法是一种单源最短路径算法，用于求解某一点到其它所有点的最短路径。以下是C++实现Dijkstra算法的示例代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大
const int MAXN = 1000; // 最大点数

int n, m; // n为点数，m为边数
int dis[MAXN]; // dis[i]表示源点到i点的最短距离
bool vis[MAXN]; // vis[i]记录i点是否已被访问
int map[MAXN][MAXN]; // 存储图的邻接矩阵

void dijkstra(int start) {
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[start] = 0;
    for (int i = 0; i < n; i++) {
        int x, m = INF;
        for (int j = 0; j < n; j++) { // 找到未访问的最近点
            if (!vis[j] && dis[j] < m) {
                m = dis[j];
                x = j;
            }
        }
        vis[x] = true;
        for (int j = 0; j < n; j++) { // 更新距离
            if (!vis[j] && dis[j] > dis[x] + map[x][j]) {
                dis[j] = dis[x] + map[x][j];
            }
        }
    }
}

int main() {
    // 输入图的点数和边数
    cin >> n >> m;

    // 初始化邻接矩阵
    memset(map, INF, sizeof(map));
    for (int i = 0; i < n; i++) {
        map[i][i] = 0;
    }

    // 输入边的信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        map[u][v] = map[v][u] = w; // 无向图
    }

    // 求解最短路径
    dijkstra(0);

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;

    return 0;
}

在上述代码中，我们首先定义了一个邻接矩阵来存储图的信息。接着，我们通过输入点数和边数以及边的信息来初始化邻接矩阵。然后，我们定义了一个dis数组来记录源点到其它点的最短距离，以及一个vis数组来记录每个点是否已被访问。接着，我们实现了Dijkstra算法的核心部分，即在未访问的点中找到离源点最近的点，并更新其它点的最短距离。最后，我们输出了源点到其它点的最短路径。