专栏首页恰童鞋骚年数据结构基础温故-5.图(下):最短路径

数据结构基础温故-5.图(下):最短路径

图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径。例如在交通网络中经常会遇到这样的问题:两地之间是否有公路可通;在有多条公路可通的情况下,哪一条路径是最短的等等。这就是带权图中求最短路径的问题,此时路径的长度不再是路径上边的数目总和,而是路径上的边所带权值的和。带权图分为无向带权图和有向带权图,但如果从A地到B地有一条公路,A地和B地的海拔高度不同,由于上坡和下坡的车速不同,那么边<A,B>和边<B,A>上表示行驶时间的权值也不同。考虑到交通网络中的这种有向性,本篇也只讨论有向带权图的最短路径。一般习惯将路径的开始顶点成为源点,路径的最后一个顶点成为终点。

一、单源点最短路径

  单源点最短路径是指给定一个出发点(源点)和一个有向图,求出源点到其他各顶点之间的最短路径。对于下图左边所示的有向图G,设顶点0为源点,则其到其他各顶点的最短路径如下图右边所示。

  从上图中可以看出,从源点0到终点4一共有4条路径:

  (1)0→4      路径长度:90

  (2)0→3→4     路径长度:90

  (3)0→1→2→4    路径长度:70

  (4)0→3→2→4    路径长度:60

  可以看出,源点0到终点4的最短路径为第(4)条路径。为了求出最短路径,前人们已经做很多工作,为我们奉献了两个重要的算法:Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德)算法,下面我们就来看看这两个算法。

二、Dijkstra算法

2.1 算法思想

Dijkstra在对最短路径的求解方式做了大量的观察之后,首先提出了按路径长度递增产生与顶点之间的路径最短的算法,以他的名字称之为Dijkstra算法。

Dijkstra算法的基本思想是:将图中顶点的集合分为两组S和U,并按最短路径长度的递增次序依次将集合U中的顶点加入到S中,在加入的过程中,总保持从原点v到S中各顶点的最短路径长度不大于从原点v到U中任何顶点的最短路径长度。

  Dijkstra算法采用邻接矩阵存储图的信息并计算源点到图中其余顶点的最短路径,如下图所示。

2.2 算法实现

  (1)代码实现

        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[i] = cost[v, i];
                // 初始化路径集
                if (cost[v, i] > 0)
                {
                    // 如果源点与顶点存在边
                    path[i] = v;
                }
                else
                {
                    // 如果源点与顶点不存在边
                    path[i] = -1;
                }
            }

            s[v] = 1;   // 将源点加入集合S
            path[v] = 0;

            for (int i = 0; i < n; i++)
            {
                int u = 0;  // 指示剩余顶点在dist集合中的最小值的索引号
                int minDis = int.MaxValue; // 指示剩余顶点在dist集合中的最小值大小

                // 01.计算dist集合中的最小值
                for (int j = 0; j < n; j++)
                {
                    if (s[j] == 0 && dist[j] > 0 && dist[j] < minDis)
                    {
                        u = j;
                        minDis = dist[j];
                    }
                }

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

                // 02.计算源点经过顶点u到其余顶点的距离
                for (int j = 0; j < n; j++)
                {
                    // 如果顶点不在集合S中
                    if (s[j] == 0)
                    {
                        // 加入的顶点如与其余顶点存在边,并且重新计算的值小于原值
                        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 + Environment.NewLine + "SUM:");
                    Console.WriteLine("路径长度为:{0}", dist[i]);
                }
            }
        }

        static void GetPath(int[] path, int i, int v)
        {
            int k = path[i];
            if (k == v)
            {
                return;
            }

            GetPath(path, k, v);
            Console.Write(k + "→");
        }

  这里经历了三个步骤,第一步是构造集合U,第二步是寻找最短路径,第三步是重新计算替换原有路径。

  (2)基本测试

  这里要构造的有向带权图如下图所示:

        static void DijkstraTest()
        {
            int[,] cost = new int[5, 5];
            // 初始化邻接矩阵
            cost[0, 1] = 10;
            cost[0, 3] = 30;
            cost[0, 4] = 90;
            cost[1, 2] = 50;
            cost[2, 4] = 10;
            cost[3, 2] = 20;
            cost[3, 4] = 60;
            // 使用Dijkstra算法计算最短路径
            Dijkstra(cost, 0);
        }

  运行结果如下图所示:

  从图中可以看出,从源点0到终点4的最短路径为:0→3→2→4,该路径长度为60。

三、Floyd算法

3.1 算法思想

Floyd(弗洛伊德)算法提出了另外一种用于计算有向图中所有顶点间的最短路径,这种算法成为Floyd算法,它的形式较Dijkstra算法更为简单。

  Floyd算法仍然使用邻接矩阵存储的图,同时定义了一个二维数组A,其中每一个分量A[i,j]是顶点i到顶点j的最短路径长度。另外还使用了另一个二维数组path来保存最短路径信息。Floyd算法的基本思想如下:

(1)初始时,对图中任意两个顶点Vi和Vj,如果从Vi到Vj存在边,则从Vi到Vj存在一条长度为cost[i,j]的路径,但该路径不一定是最短路径。初始化时,A[i,j]=cost[i,j]。 (2)在图中任意两个顶点Vi和Vj之间加入顶点Vk,如果Vi经Vk到达Vj的路径存在并更短,则用A[i,k]+A[k,j]的值代替原来的A[i,j]值。 (3)重复步骤(2),直到将所有顶点作为中间点依次加入集合中,并通过迭代公式不断修正A[i,j]的值,最终获得任意顶点的最短路径长度。

3.2 算法实现

  (1)代码实现

        static void Floyd(int[,] cost, int v)
        {
            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++)
                {
                    // 辅助数组A和path的初始化
                    A[i, j] = cost[i, j];
                    path[i, j] = -1;
                }
            }

            // Flyod算法核心代码部分
            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;
                            }
                        }
                    }
                }
            }

            // 打印最短路径及路径长度
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (A[i, j] == 0)
                    {
                        if (i != j)
                        {
                            Console.WriteLine("从{0}到{1}没有路径!", i, j);
                        }
                    }
                    else
                    {
                        Console.Write("从{0}到{1}的路径为:", i, j);
                        Console.Write(i + "→");
                        // 使用递归获取指定顶点的路径
                        GetPath(path, i, j);
                        Console.Write(j + "     ");
                        Console.WriteLine("路径长度为:{0}", A[i, j]);
                    }
                }
                Console.WriteLine();
            }
        }

        static void GetPath(int[,] path, int i, int j)
        {
            int k = path[i, j];
            if (k == -1)
            {
                return;
            }

            GetPath(path, i, k);
            Console.Write(k + "→");
            GetPath(path, k, j);
        }

  (2)基本测试

        static void FloydTest()
        {
            int[,] cost = new int[5, 5];
            // 初始化邻接矩阵
            cost[0, 1] = 10;
            cost[0, 3] = 30;
            cost[0, 4] = 90;
            cost[1, 2] = 50;
            cost[2, 4] = 10;
            cost[3, 2] = 20;
            cost[3, 4] = 60;
            // 使用Flyod算法计算最短路径
            Floyd(cost, 0);
        }

  运行结果如下图所示:

参考资料

(1)程杰,《大话数据结构》

(2)陈广,《数据结构(C#语言描述)》

(3)段恩泽,《数据结构(C#语言版)》

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构基础温故-5.图(中):最小生成树算法

    图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

    Edison Zhou
  • 剑指Offer面试题:5.重建二叉树

      在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值...

    Edison Zhou
  • 你必须知道的指针基础-7.void指针与函数指针

      void *表示一个“不知道类型”的指针,也就不知道从这个指针地址开始多少字节为一个数据。和用int表示指针异曲同工,只是更明确是“指针”。

    Edison Zhou
  • 最长公共子序列(LCS)

    mathor
  • python 标准库大全

    郭大侠
  • 2.4 图形硬件

    这一节中主要阐述图形硬件的相关知识,主要包括 GPU 中数据的存放硬件, 以及各类缓冲区的具体含义和用途,如:z buffer(深度缓冲区)、stencil b...

    代码咖啡
  • 利用Electron简单撸一个Markdown编辑器

    Markdown 是我们每一位开发者的必备技能,在写 Markdown 过程中,总是寻找了各种各样的编辑器,但每种编辑器都只能满足某一方面的需要,却不能都满足于...

    叶梅树
  • Heartrate:如追综心跳般实时动态可视化监测 Python 程序运行

    项目地址:https://github.com/alexmojaki/heartrate

    崔庆才
  • Python变量与数据类型

    1 Python中数据类型 1、整数 Python可以处理任意大小的整数,当然包括负整数,在Python程序中,整数的表示方法和数学上的写法一模一样,例如:,,...

    企鹅号小编
  • 从零开始学习PYTHON3讲义(二)把Python当做计算器

    上一讲我们说过了如何启动Python IDLE集成开发学习环境,macOS/Linux都可以在命令行执行idle3。Windows则从开始菜单中去寻找IDLE程...

    俺踏月色而来

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动