数据结构主讲人：杨丹常州信息职业技术学院5.6最短路径

在一个图中，若从一个顶点到另外一个顶点存在路径，路径长度就是一条路径上所经过的边的数目。图中从一个顶点到另外一个顶点可能存在多条路径，路径长度最短的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。引言Introduction

Part01带权图的最短路径

在一个带权图中，若从一个顶点到另外一个顶点存在一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个顶点到另外一个顶点可能存在着许多条路径，带权路径长度值最小的那条路径称为最短路径，其带权路径长度叫做最短路径长度或最短距离。带权图可以分为有向