Dijkstra经典算法注意点
前言
迪杰斯特拉算法，经典模板如下：
void dij(int s)
{
for(int i=1; i<=n; i++)
dis[i]=road[s][i];
vis[s]=1;
dis[s]=0; //这句话也可以不加
for(int i=1; i<n; i++)
{
int tmp=inf, k;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j] < tmp)
{
tmp=dis[j];
k=j;
}
}
vis[k]=1;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j] > dis[k]+road[k][j])
dis[j]=dis[k]+road[k][j];
}
}
}
偶然发现的问题——让我受益匪浅
迪杰斯特拉算法在最短路中的地位无可撼动，也是小白进阶过程中必学的算法之一。对于迪杰斯特拉的模板，网上可以说很多，但是笔者最近在做一道题时使用了Dijkstra算法，而且是最简单的那种，使用的代码就是上面那种，但是在输入数据时发生了错误，在评测时出现了Runtime Error(Access_Violation)，我当时以为是数组发生了越界，但是看了看数据量，自己开大足够大啊，问题一点点逼近，最后调试发现一个”惊天“秘密。且看下面的代码：
const int inf=0x3f3f3f3f;
void dij(int s)
{
for(int i=1; i<=n; i++)
dis[i]=road[s][i];
vis[s]=1;
dis[s]=0; //这句话也可以不加
for(int i=1; i<n; i++)
{
int tmp=inf, k;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j] < tmp)
{
tmp=dis[j];
k=j;
}
}
if(tmp==inf) //如果没有更新成功，那么接下来也不会再次更新，可以结束循环了。
break;
vis[k]=1;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j] > dis[k]+road[k][j])
dis[j]=dis[k]+road[k][j];
}
}
}
和上面相比就多了一句话，然而我的代码却过了，为什么呢？
if(tmp==inf) //如果没有更新成功，那么接下来也不会再次更新，可以结束循环了。
break;//这句话以后就必须加上了。
原因在于，如果在第一轮寻找最小值时没有找到最小值，就是tmp的值还是inf时，如果没有这句话会怎样？需要注意的是，这时k的值还是不确定的，k的值任意，就有可能越界，而且很有能越界，导致问题，那为什么以前使用没有出现问题呢，这是因为c++开始初始化一般会初始化为零，或者因为数组开的大，k的值还在数组范围内，但是如果多次调用这个函数，而这一次调用的数据范围比上一次要小的话，这个k很有可能还是上次的值（因为编译器优化的原因），那么就有可能越界。
这段代码笔者在《啊哈！算法》和《算法竞赛入门经典》中都看到过，书中都是没有添加上面那句判断语句，只是提到了可以使用而已，发现这中情况后，这句判断语句是一定要加了。
谨以记录，前车之鉴，后事之师。