旅行商问题著名算法简介

posted at 2021.8.31 19:28 by 风信子

 

   旅行商最短路径的解决有二个著名的算法:迪克斯特拉(Dijkstra)和弗洛伊德(Floyed)算法。

   一、迪克斯特拉(Dijkstra)在1959年发现了一个解决无向带权图中最短通路问题的算法,其中所有的权都是正数。它依赖于一系列的迭代。通过在每次迭代里添加一个顶点来构造出特殊顶点的集合。迪克斯特拉算法使用On^3)次运算(加法和比较)来求出连通简单无向带权图里两点之间最短通路的长度。

   Dijkstra算法的基本思想是:

   将图中顶点的集合分为两组SU,并按最短路径长度的递增次序依次把集合U中的顶点加入到S中,在加入的过程中,总保持从源点vS中各顶点的最短路径长度不大于从源点vU中任何顶点的最短路径长度。

 Dijkstra算法的C#代码如下:

using System;

namespace ConsoleApp1

{

    class Program

    {

        //Dijkstra算法,cost为邻接矩阵,v为源点

        static void Dijkstra(int[,] cost,int v)

        {

            int n = cost.GetLength(1);    //顶点个数

            int[] s = new int[n];         //集合S

            int[] dist = new int[n];      //结果集

            int[] path = new int[n];      //存放路径

            for(int i = 0; i < n; i++)

            {

                //结果集初始化,将邻接矩阵源点所表示的行数据加进dist集合

                dist[i] = cost[v, i];

                if (cost[v, i] > 0)             //路径初始化

                {

                    //如果某顶点与源点存在边,则将它的前一顶点设为源点

                    path[i] = v;

                }

                else

                {

                    //如果某顶点与源点不存在边,则将它的前一顶点值设为-1

                    path[i] = -i;

                }

            }

            s[v] = 1;       //将源点加进集合S

            path[v] = 0;

            for(int i = 0; i < n; i++)

            {

                //u表示剩余顶点在dist集合中的最小值所在索引

                int u = 0, mindis = int.MaxValue;

                for (int j = 0; j < n; j++)

                {

                    //寻找dist集合中的最小值

                    if(s[j]==0 && dist[j]>0 && dist[j] < mindis)

                    {

                        u = j;

                        mindis = dist[j];

                    }

                }

                s[u] = 1;    //将抽取出的顶点放入集合S

                for(int j = 0; j < n; j++)

                {

                    if (s[j] == 0)          //如果顶点不在集合S

                    {

                        //加入的顶点与其余顶点存在边,并且新计算的值小于原值

                        if(cost[u,j]>0 && (dist[j]==0 || dist[u] + cost[u, j] < dist[j]))

                        {

                            //用更小的值代替原值

                            dist[j] = dist[u] + cost[u, j];

                            path[j] = u;

                        }

                    }

                }

            }

            //打印源点到各顶点路径及距离

           for(int i = 0; i < n; i++)

            {

                if (s[i] == 1)

                {

                    Console.Write("{0} {1}的最短路径为:", v, i);

                    Console.Write(v + "-->");

                    GetPath(path, i, v);

                    Console.Write(i);

                    Console.Write("      路径长度为:" + dist[i] + "\n");

                }

            } 

        }

        //使用递归获取指定顶点在路径上的前一顶点

        static void GetPath(int[] Path,int i,int v)

        {

            int k = Path[i];

            if (k == v)

            {

                return;

            }

            GetPath(Path, k, v);

            Console.Write(k + "-->");

        }

        static void Main(string[] args)

        {

            int[,] cost = new int[5, 5];

            //图的初始化

            cost[0, 1] = 100;

            cost[0, 3] = 300;

            cost[0, 4] = 900;

            cost[1, 2] = 500;

            cost[2, 4] = 100;

            cost[3, 2] = 200;

            cost[3, 4] = 600;

            Dijkstra(cost, 0);           

        }

    }

} 

   二、弗洛伊德(Floyed)提出了另一种算法,用于计算有向图中所有顶点间的最短路径,称为弗洛伊德算法,它的时间复杂度依然为On^3),但形式上更为简单。弗洛伊德算法仍然使用邻接矩阵存储的图,同时定义了一个二维数组A,其每一个分量A[i,j]是顶点i到顶点j的最短路径长度。另外还使用了另一个二维数组path来保存最短路径信息。

 Floyed算法的基本思想是:

   (1)初始时,对图中任意两个顶点ViVj,如果从ViVj存在边,则从ViVj存在一条长度为cost[i,j]的路径,但该路径不一定是最短路径。初始化时,A[i,j]=cost[i,j]

   (2)在图中任意两个顶点ViVj之间加入顶点Vk,如果ViVk到达Vj的路径存在并更短,则用A[i,k]+A[k,j]的值代替原来的A[i,j]值。

   (3)重复步骤(2),直到将所有顶点作为中间点依次加入集合中,并通过选代公式不断修正A[i,j]的值,最终获得任意顶点间的最短路径长度。 

  Floyed算法的C#代码如下:

using System;

namespace ConsoleApp1

{

    class Program1

    {

        //Floyed算法

        static void Floyed(int[,] cost,int firstPath)

        {

            int n = cost.GetLength(1);    //图中顶点个数

            int[,] A = new int[n, n];         //存放最短路径长度

            int[,] path = new int[n, n];      //存放最短路径信息

            for (int i = 0; i < n; i++)

            {

                for (int j = 0; j < n; j++)

                {

                    //辅助数组Apath的初始化

                    A[i, j] = cost[i, j];

                    path[i, j] = -1;

                }

            }

            //弗洛伊德算法核心代码

            for(int k = 0; k < n; k++)

            {

                for(int i = 0; i < n; i++)

                {

                    for(int j = 0; j < n; j++)

                    {

                        //如果存在通过中间点k的路径

                        if(i!=j && A[i,k]!=0 && A[k, j] != 0)

                        {

                            //如果加入中间点k后的路径更短

                            if(A[i,j]==0 || A[i, j] > A[i, k] + A[k, j])

                            {

                                //用新路径代替原路径

                                A[i, j] = A[i, k] + A[k, j];

                                path[i, j] = k;                           

                            }

                        }

                    }

                }

            } 

            //打印最短路径及路径长度

            if (firstPath==1)

            {

                for(int j = 0; j < n; j++)

                {

                    if (A[firstPath, j] == 0)

                    {

                        if (firstPath != j)

                        {

                            Console.Write("{0} {1}没有路径\n",firstPath,j);

                        }

                    }

                    else

                        {

                            Console.Write("{0} {1}的路径为:", firstPath, j);

                            Console.Write(firstPath + "-->");

                            GetPath(path, firstPath, j);

                            Console.Write(j);

                            Console.Write("      路径长度为:" + A[firstPath,j] + "\n");

                        }

                    }

                    Console.WriteLine();                      

            } 

        }

        //使用递归获取指定顶点的路径

        static void GetPath(int[,] Path, int i, int j)

        {

            int k = Path[i,j];

            if (k == -1)

            {

                return;

            }        

            Console.Write(k + "-->");

            GetPath(Path,k,j);

        }

        static void Main(string[] args)

        {

            int[,] cost = new int[5, 5];

            //图的初始化

            cost[0, 1] = 100;

            cost[0, 3] = 300;

            cost[0, 4] = 900;

            cost[1, 2] = 500;

            cost[2, 4] = 100;

            cost[3, 2] = 200;

            cost[3, 4] = 600;

            Floyed(cost,0); 

        }

    }

}

 

(最后编辑时间20210907 15:15) 


Tags: , , , ,

IT技术

Add comment

  Country flag

biuquote
微笑得意调皮害羞酷大笑惊讶发呆喜欢可怜尴尬闭嘴噘嘴皱眉伤心抓狂呕吐坏笑漫骂发怒
Loading