Next mission: Dijkstra

上一个post里描述了Floyd-Warshall 算法，它解决了每对顶点间的最短路径问题，其复杂度为O(V³)。当然，这个复杂度比较大，并且如果我们只需要求一对顶点间的最短路径，这是不必要的。因此我们研究单源最短路径问题。解决这类问题常用的算法有我们将要看到的Dijkstra 和另一个比较猥琐的SPFA。

这个Dijkstra 算法的限制是，图中不能含有负权边。SPFA没有这一限制，但如果已知图中没有负权边，通常优先选择Dijkstra。我想主要原因在于Dijkstra 的复杂度比较稳定，一个很简单的实现，可以稳定的为O(V²)。很明显这要快于Floyd-Warshall，不然它也没什么价值。对稀疏图的优化可以达到O(VlgV + ElgV)的复杂度，但我不用，因为如果碰上稠密图或是完全图，时间反而多了。它的竞争对手SPFA 复杂度一般为O(E)，不过某些情况下会变成O(VE)。这更危险。

下面是一个能正常运行的实现，由于较复杂，列出的内容较多。

int G[nmax][nmax], ans[nmax], pred[nmax];
bool processed[nmax];
int n, s;

int find_min()
{
 int i, min_id = _infty;
 for (i=1;i<=n;++i)
   if (!processed[i]&&ans[i]<ans[min_id])
     min_id=i;
 processed[min_id]=true;
 return min_id;
}

void relax(int a, int b)
{
 if (ans[a]+G[a][b] < ans[b])
   ans[b]=ans[a]+G[a][b], pred[b]=a;
}

void dijk_calc()
{
 int i;
 for (i=1;i<n;++i) //loops exactly n-1 times.
   {
     int p=find_min();
     int j;
     for (j=1;j<=n;++j) //for each vertex \in adj_p
 if (G[p][j])
   relax(p, j);
   }
}

前面所说的优化可以修改find_min()使用堆或是RMQ实现。尽管这是一个好算法，遇到负权边时也不得不换成SPFA了。有时间我会简要说明一下，extremely sleepy now.

Bonne nuit!