手动模拟Dijkstra求最短路的例子
为什么利用t = -1?
其实不用也可以,t = -1 只是代码看起来更加优雅一些
我们的本质目的是:在未确认的点中找一个最小的dist值,
t=-1只是让循环的时候,
遇到第一个为确认的点的时候(st[j]=false)时,t就等于这个j,
剩下的就是正常的从一个数组中找最小值的办法。
我们平时求一个数组中的最小值就是先假定第一个数时最小的,
然后一一比较,这里的关键就是多了一个条件,
得是st[j] = false 中的最小值,所以增设t = -1
不用t = -1 的代码如下(所以可以看出y总的板子确实优雅)
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 初始化第一个点的距离
// 遍历n个点
for(int i = 0; i < n; i ++ )
{
int t;
// 从前往后循环,找到第一个没确认的点的下标,这个就是t的初值,找到后就可以break循环
for(int j = 1; j <= n; j ++ )
if(!st[j])
{
t = j;
break;
}
// 再次遍历一遍,就是从一个数组中找最小值的方法一样了
for(int j = t; j <= n; j ++ ) // 直接从t开始,因为t是第一个没确定最小值的点,只有确定了最小值的点,st[j] = true,所以t之前的点肯定都已经确定是最小值了,没必要再比较大小
if(!st[j] && dist[j] < dist[t])
t = j;
st[t] = true; // 将这个最小值的点设置为确定
// 更新剩余未确认的点的最短距离
for(int j = 1; j <= n; j ++ )
if(!st[j])
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1; // memset按字节赋值,所以赋值0x3f(一个字节0x3f),int四个字节,所以相当于0x3f3f3f3f
return dist[n];
}
为什么只循环n - 1次也可以?
因为Dijkstra算法的是每一趟循环可以确定一个点到源点的最短距离,所以当n - 1 趟循环时,找到倒数第二个未确认的点后,会根据这个点,来更新最后一个点的距离,这个更新后的点的距离就是这个点到源点的最短距离。每次循环只是找到一个最短距离的点,然后更新其余点的距离信息,所以第n次循环,找到第n个待更新的点,但是后面没有其他点待更新了,所以没必要循环。