课堂截图
注释代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N]; //稠密图一般使用邻接矩阵
int dist[N]; //记录每个节点距离起点的距离
bool st[N]; //True表示已经确定最短路 属于s集合
int dijkstra() {
//所有节点距离起点的距离初始化为无穷大
memset(dist, 0x3f, sizeof dist);
//起点距离自己的距离为零
dist[1] = 0;
//迭代n次,每次可以确定一个点到起点的最短路
for (int i = 0; i < n; ++i) {
int t = -1;
//t的作用?
for (int j = 1; j <= n; ++j) {
//不在s集合,并且
//如果没有更新过,则进行更新, 或者发现更短的路径,则进行更新
if (!st[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
//加入到s集合中
st[t] = true;
//找到了距离最小的点t,并用最小的点t去更新其他的点到起点的距离
for (int j = 1; j <= n; ++j) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
// 如果起点到达不了n号节点,则返回-1
if (dist[n] == 0x3f3f3f3f) return -1;
// 返回起点距离n号节点的最短距离
return dist[n];
}
int main() {
cin >> n >> m;
//所有节点之间的距离初始化为无穷大
memset(g, 0x3f, sizeof g);
// 0x3f 0x3f3f3f3f 的区别?
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); //如果有重边,请保留权值最小的一条边
}
cout << dijkstra() << endl;
return 0;
}
自问自答hh
int t = -1;
//t的作用?
一开始t的赋值是-1
如果t没有被更新,
那么要更新一下t
// 0x3f 0x3f3f3f3f 的区别?
memset 按字节赋值,所以memset 0x3f 就等价与赋值为0x3f3f3f3f,
朴素版与堆优化版时间复杂度比较
朴素版时间复杂度$O(n^2)$
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j; // O(n) * O(n) -> O(n^2)
}
st[t] = true; // O(n) * O(1) -> O(n)
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]); //O(n) * O(n) -> O(n^2)
}
}
堆优化版时间复杂度$O(mlog(n))$
//遍历大部分的边
while (heap.size()) {
auto t = heap.top(); //O(m) * O(1) -> O(m)
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver])continue;
st[ver] = true; //O(m) * O(1) -> O(m)
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
heap.push({dist[j], j});
// 堆的插入操作时间复杂度是 O(log(n))
// O(m) * O(log(n)) -> O(mlog(n))
}
}
}
问的是t的作用 回答了 对t的操作 (地铁老人手机)
谢谢你省流
谢谢你省流侠
t=-1的作用反过来想想,要是没有那一句话,那么d[t]也就是d[-1]就直接没意义了
遇到的问题
1.
if(!st[j] && (t==-1 || dist[t]>dist[j])
//寻找最近的点为什么这个判断语句可以找到最近的点?
提示:思考一下使用用for循环求数组最小值或最大值的步骤
感谢讲解,基于上面,我也像讲解一下我的理解:进来for( i )这一时刻,(计算机)不知道跟谁 ” 可以 ” 是最短的,因为还没懂state[j]的状态。俗的讲:不能确定t(表示节点)的具体值,所以就索性用其他的值表示(除了节点值之外,可以等于0,-1,-10,100都行)未定。等获得足够的信息,既符合state[j] 、 d[] 后, 才开始更新
t = -1的理解:进来for( i )这一时刻,(计算机)不知道跟谁 ” 可以 ” 是最短的,因为还没懂state[j]的状态。俗的讲:不能确定t(表示节点)的具体值,所以就索性用其他的值表示(除了节点值之外,可以等于0,-1,-10,100都行)未定。等获得足够的信息,既符合state[j] 、 d[] 后, 才开始更新
t的值个人见解:要结合判断条件解释:这个t是本轮要找到的 s集合外最短路径最小的点。首先要变成 s集合外的一点,之后再根据距离大小不断更新成那个最小的点,达到前者的条件就是t为初始值并且找到S集合外一点的时候。但是 t不能初始化成随便一个点,因为不知道这个点在S里还是S外,所以为-1
那下面t==-1是什么作用呢 没懂
就是判断是不是初始状态
豁然开朗,t只是一个中介点!主要有两个作用!
1. 判断 j 遍历的点中这一个点有没有用过
2. 如果用过,就将 这一个 点的值(j) 赋给t,用 t 完成接下来一系列操作,如更新 起点到 j 的最短距离
orz
t是dist 数组中没有确定最短路径的节点中距离源点最近的点么?
好兄弟啊
不一定每次都能确定一个点的最小距离吧,有时候不止一个,也有时候一个都确定不了
那么y总的n2+m是什么意思
赞赞赞
为什么要memset(g, 0x3f, sizeof g),后面不是都读入各个点之间的距离了吗
有的点之间是没有边的
知道了,谢谢
为什么我把g[i][j] = 0(i== j的时候)就错了呢
其实迭代n-1次就够了
如果t等于-1怎么办!
t不会等于-1,最坏情况=1
t在第一次循环的时候就变成了任意一个未确定最短距离的点,之后的循环中,是在未确定最短距离的点中,选出一个最短距离最小的点。
t的含义是未确定最短距离,且在未确定最短距离的所有点中,距离起点最近的点(也就是dist[t]最小的点)。
不像之前比较一些值中的最小值时,可以先随意指定一个值为最小值t,再挨个比较,保证t中的值始终最小,比较结束之后,t中的就是最小值。在这里之所以写成t = -1,是因为如果随意指定一个点为离起点距离最短的点,那么无法保证这个点一定是未确定最短距离的点。假如这个点恰好是一个确定了最短距离,且在所有未确定最短距离的点中,其最短距离最小的点,那么就把这个点的最短距离设置了两遍。
自环为啥也能更新成无穷大?
图借走了
大佬好详细