写一个Dijkstra算法代码

Dijkstra算法代码：// 初始化
int dist[MAX];
bool visited[MAX];

for (int i = 0; i < MAX; i++)
dist[i] = INT_MAX, visited[i] = false;

// 将起点加入已访问
dist[start] = 0;
visited[start] = true;

// 遍历每一条边
for (int i = 0; i < edge_num; i++) {
int u = edges[i].first;
int v = edges[i].second;
int weight = edges[i].weight;

// 如果起点已访问，则考虑当前边
if (visited[u] == true) {
// 如果从起点到终点的距离比当前距离大，则更新
if (dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}

相关问题

用python写一个dijkstra算法

好的，以下是用 Python 写的 Dijkstra 算法样例代码：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    
    return distances

其中，graph 是一个字典，存储了图中每个节点和它们的邻居及其权重信息，start 是从哪个节点开始计算最短路径。函数返回一个字典，包含从 start 节点出发到图中每个节点的最短路径距离。

希望这个算法能帮到你！

c++ 写一个dijkstra算法实现

### 回答1：
好的，关于 Dijkstra 算法的实现，我可以给你一些指导。

Dijkstra 算法是一种解决单源最短路径问题的经典算法。它的主要思路是从源点开始，逐步扩展搜索的范围，直到覆盖所有节点为止。在搜索的过程中，维护每个节点到源点的最短距离，并选择当前距离最小的未被访问的节点进行扩展。具体实现时，可以使用一个优先队列（例如 C++ STL 中的 priority_queue）来维护未被访问的节点，以便每次选择距离最小的节点进行扩展。

以下是一个简单的 C++ 实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<Edge> adj[1000];
int dist[1000];
bool vis[1000];

void dijkstra(int s) {
    memset(dist, INF, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (const auto& e : adj[u]) {
            int v = e.v, w = e.w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
    return 0;
}

这段代码实现了 Dijkstra 算法，并且支持读入有向图的边权信息，计算从源点 s 到所有点的最短距离，并输出结果。具体来说，首先初始化距离数组 dist 为正无穷，将源点的距离设为 0，然后使用一个优先队列 pq 维护未被访问的节点，每次选择距离最小的节点 u 进行扩展，并更新其它节点的距离。在更新节点距离时，需要判断是否需要松弛（relax）操作，即将当前节点 u 到其邻居节点 v 的边权加到距离 dist[v]

### 回答2：
Dijkstra算法是一种解决单源最短路径问题的经典算法。它通过逐步找到从起点到其他所有顶点的最短路径来实现。

具体实现Dijkstra算法的步骤如下：
1. 创建一个顶点集合和一个距离集合。初始化距离集合，起点距离为0，其他顶点距离为无穷大。
2. 在顶点集合中选择一个顶点作为当前顶点，初始化时选择起点。
3. 遍历当前顶点的所有邻接顶点，计算从起点经过当前顶点到达邻接顶点的距离，如果这个距离小于邻接顶点的当前最短距离，更新邻接顶点的最短距离。
4. 从距离集合中选择一个未被访问的顶点，即距离最小的顶点，作为新的当前顶点，重复步骤3。
5. 重复步骤3和4，直到所有顶点都被访问过或者没有可以选择的顶点为止。

下面是一个用300字回答的Dijkstra算法实现的伪代码：

1. 初始化距离集合，将起点距离设为0，其他顶点距离设为无穷大。
2. 创建一个顶点集合，将起点加入集合中。
3. while (顶点集合非空) {
4. 选择距离集合中最小的顶点作为当前顶点。
5. 遍历当前顶点的所有邻接顶点 {
6. 计算通过当前顶点到达邻接顶点的距离。
7. 如果这个距离小于邻接顶点的当前最短距离，更新邻接顶点的最短距离。
8. }
9. 将当前顶点从顶点集合中移除。
10. }
11. 输出最短距离集合。

这个伪代码描述了Dijkstra算法的基本流程，具体实现时可能需要添加一些数据结构或辅助函数来实现顶点、距离集合等的管理。实际代码实现时可以根据具体语言和需要进行适当调整。

### 回答3：
Dijkstra算法是一种用于求解单源最短路径的图算法。它适用于带有非负权值的有向图或无向图。

下面是一个简单的Dijkstra算法的实现：

1. 创建一个数组distances，用于存储起始节点到每个节点的最短路径距离。初始时，将起始节点的距离设置为0，将其他节点的距离设置为正无穷大。
2. 创建一个集合visited，用于记录已经访问过的节点。
3. 创建一个优先队列，用于按照节点距离的大小进行排序。
4. 将起始节点加入到优先队列中。
5. 当优先队列不为空时，重复以下步骤：
1) 从优先队列中取出一个节点node，将其标记为已访问。
2) 遍历节点node的邻居节点neighbor：
- 计算起始节点到neighbor节点的距离：distance = distances[node] + edge(node, neighbor)。其中edge(node, neighbor)表示node到neighbor的边的权值。
- 如果distance小于distances[neighbor]，更新distances[neighbor]的值，并将neighbor节点加入到优先队列中。
6. 循环结束后，distances数组中存储的就是起始节点到每个节点的最短路径距离。

此外，还可以使用一个数组predecessors来记录最短路径中每个节点的前驱节点，以便后续构建最短路径。

以上就是一个简单的Dijkstra算法的实现。然而，实际应用中可能会有更多的优化措施，例如使用堆代替优先队列，以提高算法的效率。