距离向量算法
-
基本思想:每个节点构造一个包含到所有其他节点的“距离”的一个向量,并将该向量分发给与其直接相连的节点,节点根据收到的距离向量计算到其他所有节点的最短路径。
算法:Bellman-Ford算法
算法实现(Floyd)
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N; k++)
dis[j][k]=min(dis[j,k],dis[j][i]+dis[i][k]+value[i]);这个算法基于动态规划,即将从j到k的路径按照是否经过i分为两种,结果一定是这两者中的最小值。然后循环遍历每一对结点。
用这个来理解距离向量算法:结点j知道目前他到其他节点的距离,然后他收到了i传来的距离向量,他根据这个向量来更新自己向量表中的内容