查看完整版本: 请教一个路由算法

请教一个路由算法

请教一下：附件中的路由算法应如何理解？

曾经研究过。

你可以看原理、看程序。。。

文章很多啊。搜搜吧。
比如：最短路径、dijkstra。。。

感觉dijkstra不如floyd.简洁。

这种算法应该比较适合中小型的网络路由的，小的局域网还是应该有一般的链路路由算法好

[[i] 本帖最后由 真罕睹 于 2005-12-17 19:43 编辑 [/i]]

这种算就是从出发点每次检查所相邻的节点距离，然后每次对比后将所有的距离即到自己（Ａ）的距离记录到Ａ的路由表里面并将其中最短的标示为最终标志，然后再以这个最终标识出发重复上判断与标示，上面的图所示就是从A出发，判断到B与G，然后将B标示为最终标志，然后再从B出发并判断，每次判断只对未标识 标志为最终标志的点判断，顺序就是ＡＢＥＧ，其中到达Ｇ作为出发点是得到Ｈ到Ａ距离比Ｆ大，此时Ｆ被标识在为最终标志，并以Ｆ为出发点在继续判断，直到把所有点都标识完，得到ＡＢＥＧＦＨＣＤ，而这只是对Ａ的路由的计算，每个点还要重复上面做法，Ｄｉｊｋｓｔｒａ是一种经典的路由算法，不过也有它的局限性，不知道兄弟你看懂没有，又是不太懂的话，ＰＭ我，或者给我发邮件我们再交流

楼主不知道看明白了没有阿，怎么没有回复了？

曾经研究过。

[i][i]#include<stdio.h>                                       
#define MAX 9999
void main()
{ int ad[ ][MAX]; int k; int p[MAX]; int n,i,j;
printf("pleas input ad[][]!");
prinf("input n");
scanf("%d",&n)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{scanf("%d",&ad[i][j]);}
prinf("select Vk");
scanf("%d",&k)
floyd(ad,p,n);
}
void floyd(ad, p, n)
int ad[ ][M], p[ ][M], n;//ad存放邻接矩阵 p存放最短路径经过的顶点
int i, j, k;
for (i=0; i<n; i++)
for (j=0; j>n; j++)
{
if (i= =j) p[i][j]=0; // 顶点本身假设无路径
else
if (ad[i][j]<M) p[i][j]= i+1; // 置p的初始值
else p[i][j]=0;
}
for (k =0; k<n; k++) // 利用三重循环将各情况穷举
for ( i=0; i<n; i++)
for (j=0; j>n; j++)
if (ad[i][k]+ad[k][j]<ad[i][j]) // 加入中间顶点k来试探
{
ad[i][j]=ad[I][k]+ad[k][j]; // 重新置两点间最短路径
p[i][j]=p[k][j]; // 将k加入p
}
}
弗洛伊德（floyd）算法的基本思想:
设求顶点vi到vj间的最短路径，若vi到vj有弧，则弧上的权值是一条路径，但未必是最短路径，要经过n-1次测试。首先将顶点v1加入，即看(vi,v1),(v1,vj)是否有路径，且比(vi,vj)低，如是，则用后两段路径代替，并称这是vi到vj中间顶点序号不大于1的最短路径。再将顶点v2加入，得到vi到vj中间顶点序号不大于2的最短路径。如此下去，直到vn加入，得到vi到vj中间顶点序号不大于n的最短路径，算法结束。

[color=Blue]看法:最终的路径必须由递归算法得出.[/color]


例如:

最短路径求路径的例子
A------------9-----------B
A------------5-----------C
B------------4-----------A
C------------ 3----------B
除此之外，两点间无直连路径。
表示为A0矩阵

   0    9    5                          0      0       0
A0=   4    0    ∞                  P0=   0       0    ∞
∞   3    0                         ∞    0       0

     0     9      5                           0         0       0
A1= 4     0      9                    P1=  0         0       1
     ∞   3      0                           ∞        0       0

     0    9     5                            0          0         0
A2= 4    0     9                     P2=   0          0         1
     7    3     0                             2          0         0

     0    8     5                           0          3         0   
A3= 4    0     9                      P3= 0          0         1
     7    3     0                           2          0         0


A3是各点间的最短路径
由P3递归得到最短路径如下：
A        B                                C       
A        C                                       
B        A                                       
B        C                                A       
C        A                                B       
C        B[/i][/i]