最短路问题之朴素Dijkstra算法（迪科斯彻算法） 适用于边的权值都为正的有向图_csdn 迪科斯

朴素Dijkstra算法（迪斯科彻算法）

1. 每次从未标记节点中选择距离出发点最近的节点， 标记， 收录进最优路径集合中。

2. 计算刚加入的节点A到邻近节点B的距离（不包括标记节点，因为标记了的节点表示已找到最短路径）

   如果 （节点A的距离 + 节点A到节点B的边长） < 节点B的距离， 就更新节点B的距离 和 前面点

适合稠密图（边数较多）,稠密图用邻接矩阵，稀疏图用邻接表

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N]; //稠密图用邻接矩阵
int dist[N]; //表示从1号点走到这个点的距离
bool st[N]; //表示每个点的最短路是否确定
int n, m;
int dijkstra() {
    //1.初始化距离
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    //2.遍历n次
    for (int i = 0; i < n; i++) {
        int t = -1;  // 便于 每次选择 与 起点 距离最小的点 （循环开始  
        for (int j = 1; j <= n; j+&#
1
2
3
4
5
6
7
8
9
10
11
12
13
14