链路状态路由算法

oasis

基本思想：每个节点都知道怎样到达他的邻节点，并通知所有节点与之直接相连的链路状态，每个节点获得完整的网络信息来建立路由表。

算法：Dijkstra

算法实现：（以一个节点a为例）
for (int i = 1; i <= N; i++)
{
  if (road[a][i] < dis[i])
    dis[i] = road[a][i];
}
dis[a] = 0;
vis[a] = 1;
for (int i = 1; i < N; i++)
{
  int l = inf;
  int b = a;
  for(int j=1;j<=N;j++)
    if (vis[j] == 0 && dis[j] < l)
    {
      l = dis[j];
      b = j;
    }
    vis[b] = 1;
    for (int j = 1; j <= N; j++)
    {
      if (vis[j] == 0 && dis[b] + road[b][j] < dis[j])
        dis[j] = dis[b] + road[b][j];
    }
}

算法思想：从一个点开始，压缩与它相连的长度，从与这个点最近的未选过的点开始反复压缩相连长度，执行n次结束。

用Dijkstra理解链路状态路由算法：节点b到a的最短距离已经被确定后，他告诉每一个节点他到a的距离，然后其他每一个节点都更新目前到a的最短距离。