JZTXT

图的应用--最短路

发布时间 2023-07-11 21:47:11作者: harper886

图的应用--最短路

最短路径问题

image-20230711092323966

最短路径与最小生成树不同,路径上不一定包含n个顶点,也不一定包含n-1条边.

image-20230711092559732

第一类问题:两点间最短路径

image-20230711092805228

第二类问题:某源点到其他各点最短路径

image-20230711093017495

两类常见最短路径问题

  1. 单源最短路径--用Dijkstra算法
  2. 所有顶点的最短路径--用floyd算法

image-20230711093305210

Dijkstra:

image-20230711093544361

Dijkstra算法

  1. 初始化

  2. 选择

  3. 更新

image-20230711094531560

Dijkstra算法:按路径长度递增次序产生最短路径

image-20230711094732620

Dijkstra算法步骤

image-20230711100806389