用来处理路径优化等问题的FLOYD等算法。

源代码在线查看: 路径优化的floyd等算法的matlab代码.txt

软件大小: 6 K
上传用户: face137
关键词: FLOYD 路径 算法
下载地址: 免注册下载 普通下载 VIP

相关代码

				
				
				
				路径优化的Floyd,dijkstra,A*算法的matlab代码
				Floyd最短路径算法
				2006-10-20, by leon_jlu
				     在图论中经常会遇到这样的问题,在一个有向图里,求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题,在计算机网络里介绍网络层的时候好像也遇到过这个问题,记不请了... 但是书本上一律采取的是Dijkstra算法,通过Dijkstra算法可以求出单源最短路径,然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味,采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下:
				      如果有一个矩阵D=[d(ij)],其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通,那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序,通过这个距离矩阵D,把任意两个城市之间的最短与其行径的路径找出来。
				     我们可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),在检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离,因此d(ik)+d(kj)就是i到j经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从i出发经过k再到j的距离要比原来的i到j距离短,自然把i到j的d(ij)重写为d(ik)+d(kj),每当一个k查完了,d(ij)就是目前的i到j的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的程序,但是仔细考虑的话,会发现是有问题的。
				
				                     for(int i=0; i				                           for(int j=0; j				                                for(int k=0; k				     
				
				     问题出在我们太早的把i-k-j的距离确定下来了,假设一旦找到了i-p-j最短的距离后,i到j就相当处理完了,以后不会在改变了,一旦以后有使i到j的更短的距离时也不能再去更新了,所以结果一定是不对的。所以应当象下面一样来写程序:
				
				                    for(int k=0; k				                         for(int i=0; i				                              for(int j=0; j				
				    这样作的意义在于固定了k,把所有i到j而经过k的距离找出来,然后象开头所提到的那样进行比较和重写,因为k是在最外层的,所以会把所有的i到j都处理完后,才会移动到下一个k,这样就不会有问题了,看来多层循环的时候,我们一定要当心,否则很容易就弄错了。
				     接下来就要看一看如何找出最短路径所行经的城市了,这里要用到另一个矩阵P,它的定义是这样的:p(ij)的值如果为p,就表示i到j的最短行经为i->...->p->j,也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后,要找最短路径就轻而易举了。对于i到j而言找出p(ij),令为p,就知道了路径i->...->p->j;再去找p(ip),如果值为q,i到p的最短路径为i->...->q->p;再去找p(iq),如果值为r,i到q的最短路径为i->...->r->q;所以一再反复,到了某个p(it)的值为i时,就表示i到t的最短路径为i->t,就会的到答案了,i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的,所以输出的时候要把它倒过来。
				     但是,如何动态的回填P矩阵的值呢?回想一下,当d(ij)>d(ik)+d(kj)时,就要让i到j的最短路径改为走i->...->k->...->j这一条路,但是d(kj)的值是已知的,换句话说,就是k->...->j这条路是已知的,所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的,当然,因为要改走i->...->k->...->j这一条路,j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj),就把p(kj)存入p(ij)。
				   下面是具体的C代码:
				   #include             
				   #include            
				   #include            
				   #define   MAXSIZE   20        
				
				   void  floyd(int [][MAXSIZE], int [][MAXSIZE], int);
				   void  display_path(int [][MAXSIZE], int [][MAXSIZE], int);
				   void  reverse(int [], int);
				   void  readin(int [][MAXSIZE], int *);
				
				   #define   MAXSUM(a, b)   (((a) != INT_MAX && (b) != INT_MAX) ? \
				                          ((a) + (b)) : INT_MAX)
				
				   void floyd(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
				   {
				       int  i, j, k;
				       for (i = 0; i < n; i++)  
				           for (j = 0; j < n; j++)
				               path[j] = i;
				       for (k = 0; k < n; k++)  
				           for (i = 0; i < n; i++) 
				               for (j = 0; j < n; j++)  
				                    if (dist[j] > MAXSUM(dist[k], dist[k][j])) 
				                    {
				                         path[j] = path[k][j]; 
				                         dist[j] = MAXSUM(dist[k], dist[k][j]);
				                    }
				   }
				
				   void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
				   {
				       int  *chain;
				       int  count;
				       int  i, j, k;
				       printf("\n\nOrigin->Dest   Dist   ath");
				       printf(  "\n-----------------------------");
				       chain = (int *) malloc(sizeof(int)*n);
				       for (i = 0; i < n; i++) 
				           for (j = 0; j < n; j++)
				           {
				               if (i != j)
				               {  
				                    printf("\n%6d->%d    ", i+1, j+1);
				                    if (dist[j] == INT_MAX) 
				                         printf("  NA    "); 
				                    else
				                    {
				                         printf("%4d    ", dist[j]);
				                         count = 0;   
				                         k = j;
				                         do
				                         {
				                             k = chain[count++] = path[k];
				                         } while (i != k);
				                         reverse(chain, count); 
				                         printf("%d", chain[0]+1); 
				                         for (k = 1; k < count; k++)
				                              printf("->%d", chain[k]+1);
				                         printf("->%d", j+1);
				                    }
				               }
				           }
				       free(chain);             
				   }
				
				   #define SWAP(a, b)  { temp = a; a = b; b = temp; }
				
				   void reverse(int x[], int n)
				   {
				       int  i, j, temp;
				       for (i = 0, j = n-1; i < j; i++, j--)
				            SWAP(x, x[j]);
				   }
				
				   void readin(int dist[][MAXSIZE], int *number)
				   {
				       int  origin, dest, length, n;
				       int  i, j;
				       char line[100];
				       gets(line);              
				       sscanf(line, "%d", &n);
				       *number = n;
				       for (i = 0; i < n; i++) 
				       {
				           for (j = 0; j < n; j++)
				                dist[j] = INT_MAX;
				           dist = 0;     
				       }
				       gets(line);              
				       sscanf(line, "%d%d%d", &origin, &dest, &length);
				       while (origin != 0 && dest != 0 && length != 0)
				       {
				          dist[origin-1][dest-1] = length;
				          gets(line);         
				          sscanf(line, "%d%d%d", &origin, &dest, &length);
				       }
				   }
				     测试程序如下所示:
				   int main(void)
				   {
				       int dist[MAXSIZE][MAXSIZE];
				       int path[MAXSIZE][MAXSIZE];
				       int n;
				       printf("\nInput the path information:");
				       printf("\n----------------------------\n");
				       readin(dist, &n);
				       floyd(dist, path, n);
				       display_path(dist, path, n);
				       getchar();
				   }
				     其中readin函数规定了输入的格式,第一列是指出有多少个城市;第二列以后每行三个数;第一个和第二个是一条路径的起点和终点,第三个数是路径的长度,最后以三个0作为输入结束条件。下面是一个输入的例子:
				              Input the path information:
				            --------------------------------------
				              4
				              1          2          5
				              2          1          50
				              2          3          15
				              2          4          5
				              3          1          30
				              3          4          15
				              4          1          15
				              4          3          5
				              0          0          0
				   对应的输出结果为:
				     Origin->Dest      Dist          Path
				  ----------------------------------------------
				        1->2             5           1->2
				        1->3            15          1->2->4->3
				        1->4            10          1->2->4
				        2->1            20          2->4->1
				        2->3            10          2->4->3
				        2->4             5           2->4
				        3->1            30          3->1
				        3->2            35          3->1->2
				        3->4            15          3->4
				        4->1            15          4->1
				        4->2            20          4->1->2
				        4->3             5           4->3
				
				Dijkstra算法是由荷兰计算机科学家艾兹格?迪科斯彻发现的。算法解决的是有向图中最短路径问题。
				
				举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
				
				Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合,而边的权重则由权重函数w: E → [0, ∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
				
				算法描述
				这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候没条边(u,v)都只被拓展一次。
				算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。 
				在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d值的顶点u。这个顶点被从集合Q中删除并返回给用户。
				1  function Dijkstra(G, w, s)
				2     for each vertex v in V[G]                        // 初始化
				3           d[v] := infinity
				4           previous[v] := undefined
				5     d[s] := 0
				6     S := empty set
				7     Q := set of all vertices
				8     while Q is not an empty set                      // Dijstra算法主体
				9           u := Extract_Min(Q)
				10           S := S union {u}
				11           for each edge (u,v) outgoing from u
				12                  if d[v] > d + w(u,v)             // 拓展边(u,v)
				13                        d[v] := d + w(u,v)
				14                        previous[v] := u
				如果我们只对在s和t之间寻找一条最短路径的话,我们可以在第9行添加条件如果满足u=t的话终止程序。
				现在我们可以通过迭代来回溯出s到t的最短路径
				1 S := empty sequence 
				2 u := t
				3 while defined u                                        
				4       insert u to the beginning of S
				5       u := previous
				现在序列S就是从s到t的最短路径的顶点集.
							

相关资源