6.3 最短路径

2023-08-07

数据结构

6.3-1 单源最短路径

1） BFS算法(无权)
2）Dijkstra(带权)
- 时间复杂度：O(|V|²)
- 不可用于有负权边的图

6.3-2 各顶点间最短路径

1）Floyd算法
- 动态规划思想：
  - 1）允许在v0中转，求最短路径
  - 2）允许在v0、v1中转，求最短路径
  - 3）允许在v0、v1、v2中转，求最短路径
  - ...
- 时间复杂度：O(|V|³)
- 不能解决负权回路的问题

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家