求最短路径算法

Ⅰ 求写最短路径算法。由A地到E地，途经B（B1，B2，B3）C（C1，C2，C3）地，基于矩阵乘法求最短路径。给出步骤

们把求A →E 的最短路分解为四个阶段A →B →C→D →E 来求解。每一个阶段可以用一个矩阵来表示，这个矩阵称为权矩阵。相邻阶段的路径可以用权矩阵的乘积来表示。但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大. 如果是求极大,改为取大运算,此时如果不同层节点间没有连接，则视它们的距离为0。
如下：
由A地到B地的距离可表示为：A[2 5 8]
由B地到C地的权矩阵可表示为
[3，6，5；7，10，8；4，9，6]
因此由A到C的权矩阵为[2，5，8][3，6，5；7，10，8；4，9，6]＝[5，8，7]
因此由A到D的权矩阵为[5，8，7)][7，5；3，4；5，2]＝[11 ，9]
由A→E的权矩阵为：[11 ，9][4，2)]=[15,11]
因此从家里到学校的最短距离为11百米，最近的路径为从A地出发经过B1地C1地D2地到达E地。

下面我们给出基于“矩阵乘法”求解最短路的算法:
第一阶段:计算出图中从起始点到终点最短路的长度.
step1 划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;
step2 依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 , …, N21) ; (若第i 层有m 个顶点;第i + 1 层有n
个顶点, 则从第i 层到第i + 1 层的权矩阵为m *n
阶) .
step3 按照我们定义的矩阵乘法计算出最短路的
数值.
第二阶段:寻找最短路所经过的中间点.
(利用第一阶段中step2 的数据) 计算出从第i 层到
终点的最短路, 对比与i21 层到终点的最短路, 从而确
定出第i 层上最短路所经过的顶点( i = 2 , …, N21) .

Ⅱ 【16】在图中，求一个顶点到其他顶点的最短路径的算法思想

在图中，求一个顶点到其他顶点的最短路径，常见的算法有Dijkstra、Bellman-Ford以及Floyd。其中，Dijkstra算法是从初始顶点开始依次向周围扩散，采用广度优先的思想，得到各个点的最短路径。时间复杂度为O(n)。

贝尔曼-福特算法则是对每一条边进行编号，然后循环遍历边，计算边的终点数据，即终点 = 起点 + 边的权值。当图有m个顶点时，需要遍历m-1次以确保结果的正确性。这种方法适用于可能存在负权重边的情况。

Floyd算法不同，它能够计算任意两个顶点之间的最短距离。其核心思想是从任意顶点i开始，通过任意顶点j，判断是否能够以更短的距离到达其他任意顶点k。这种方法的时间复杂度为O(n^2)，其中n是图中顶点的数量。

Dijkstra算法的执行步骤如下：首先将所有顶点的距离设置为无穷大，仅将起点距离设置为0。然后从起点出发，按照广度优先遍历，更新邻接点的最短距离。直到所有顶点都被确认，即完成所有最短路径的计算。

贝尔曼-福特算法的执行步骤包括：初始化边的编号，然后从第1条边开始，计算每个节点的新值。执行m-1次遍历后，即可得到正确的结果，其中m是顶点的数量。如果边的编号顺序不同，可能需要多次遍历才能得到正确结果。

Floyd算法的执行步骤较为直观，其核心在于通过遍历所有顶点对，检查是否通过其他任意顶点能够实现更短的路径。这种方法的时间复杂度为O(n^2)，适用于计算任意两个顶点之间的最短路径。

综上所述，这三种算法各有优缺点。Dijkstra算法适用于图中没有负权重边的情况，并且在时间复杂度上相对较低；贝尔曼-福特算法能够处理负权重边，但时间复杂度较高；Floyd算法适用于计算任意两个顶点之间的最短路径，但在时间复杂度上相对较慢。选择哪种算法取决于具体问题的需求和图的特性。