链路状态路由算法
-
基本思想:每个节点都知道怎样到达他的邻节点,并通知所有节点与之直接相连的链路状态,每个节点获得完整的网络信息来建立路由表。
算法: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的最短距离。