路由算法详解

文章摘要：void shortest_path(int s,int t,int path[ ]){struct state { /*当前计算的路径 */int predecessor ; /*前序节点 */int length /*从源节点到当前节点的长度*/enum {permanent, tentative} label /*标号状态*/}state[MAX_NODES];int I, k, m

路由算法详解,标签：电子电路基础,模拟电路基础,http://www.88dzw.com
void shortest_path(int s,int t,int path[ ])
{struct state {                          /*当前计算的路径 */
int predecessor ;                     /*前序节点 */
int length                                /*从源节点到当前节点的长度*/
enum {permanent, tentative} label    /*标号状态*/
}state[MAX_NODES];
int I, k, min;
struct state *
                     p;
for (p=andstate[0];p < andstate[n];p++){       /*初始化状态*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ;                                                          /* k 是初始工作节点 */
do{                                                            /*是从 k 开始的一条更好路径么？*/
for I=0; I < n; I++)                                       /*图有 n 个节点 */
if (dist[k][I] !=0 andand state[I].label==tentative){
            if (state[k].length+dist[k][I] < state[I].length){
         state[I].predecessor=k;
         state[I].length=state[k].length + dist[k][I]
      }
}
/*找到具有最小权值的暂时性节点。*/
k=0;min=INFINITY;
for (I=0;I < n;I++)
     if(state[I].label==tentative andand state[I].length <
min)=state[I].length;
     k=I;
 }
state[k].label=permanent
}while (k!=s);
/*将路径复制到输出数组*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

DV算法

DV算法也被称为Bellman-Ford路由算法和Ford-Fulkerson路由算法。在这些算法中，每个路由器都有一个路由表，用来表示到任何目的地的最佳路由。一个典型的路由器J的网络图以及路由表如下所示。

<-- -->

上一页  [1] [2] [3] [4] [5]  下一页