学习这段话并帮我写一遍意思相同的:如果我们能用点表示某事物,用点与点之间的线表示事物之间的联系,就可以把这件事物抽象地用图的方式表示出来。而运用抽象的方式将问题抽象为图,并为之建立的数学模型,就是图论。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型。至此,我们就可以运用图论的概念、理论和方法,对能抽象为图的问题进行求解。 最短路径问题可以合并为一种情况——全局最短路径问题。而计算最短路径的常用算法一共有两种:狄克斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法。Dijkstra算法研究的是从初始点到其他每一结点的最短路径,解决的是有向图中最短路径问题。其主要特点是以初始点为中心向外层层扩展,直到扩展到终点为止。Floyd算法研究的是任意两结点之间的最短路径,可以正确处理有向图或有负权的有向图(但不可存在负权回路)的最短路径问题。 本文主要运用Dijkstra算法,进行求解学生今天一天活动所走的最短路径问题。
时间: 2024-02-26 14:52:47 浏览: 120
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
把某个事物用点表示,用点与点之间的线表示它们之间的联系,就能用图的方式抽象地表示出来。抽象出来的问题可以建立数学模型,这就是图论。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型。我们可以用图论的概念、理论和方法,对抽象为图的问题进行求解。最短路径问题可以合并为一种情况——全局最短路径问题。计算最短路径的常用算法有两种:狄克斯特拉算法和弗洛伊德算法。狄克斯特拉算法解决的是有向图中从初始点到其他每一结点的最短路径问题。它以初始点为中心向外层层扩展,直到扩展到终点为止。弗洛伊德算法研究的是任意两结点之间的最短路径,可以正确处理有向图或有负权的有向图(但不可存在负权回路)的最短路径问题。本文使用Dijkstra算法,来求解学生今天一天活动所走的最短路径问题。
阅读全文