Aloha！嗨～我是少女人妻 Uerica ! 最近因为常常查演算法跟资料结构的文章，文章推荐跟 Youtube 影片首页全都变成演算法跟资料结构了，害我不得不在晚上留点时间刷刷废片啊 XDD！

路径 Path

路径顾名思义就是在图上取两个点，分别做为起点和终点，可以规划许多条起点到终点的路线，而不重复经过同一个点，就称为路径。而路径的权重就是所经过的所有边之权重和，边的权重也可以是零或负数，毕竟图只是一种储存资料的结构。

最短路径 Shortest Path

最短路径顾名思义就是起点到终点，权重最小的路径，有可能很多条，也有可能不存在，但最短路径不见得是边最少、节点最少的路径。

最短路径演算法的功能类型：

• 点对点最短路径 Point-to-Point Shortest Path：
  指定起点与终点，求出起点到终点的最短路径。

• 单源最短路径 Single Source Shortest Paths：
  指定起点，求出起点到图上每一点的最短路径。

• 全点最短路径 All Pairs Shortest Paths：
  不特别指定起点与终点，而是求出图上所有两点之间的最短路径。

重要概念

• 松弛 Relaxation : 找最短路径的演算法中，为了程序的纪录与更新，会先将每个点与点之间设为无穷大，之後若有另一条权重更小的路径再更新原本本的资料。
• 不可用在负边上：例如有一路径一 : A -> C 边权重是 5 、路径二 : A -> B -> C 边权重是 9 + -5 ，以 Dijkstra Algorithm 的特性会选择路径一，所以判断会错误，事实上权重较小的是路径二( 9 + -5 = 4 )。

戴克斯特拉演算法 Dijkstra Algorithm

戴克斯特拉演算法是最早求最短路径的演算法，属於单源最短路径演算法，也就是一个点到其他所有点的最短路径为何，不过要注意，此演算法边的权重不可是负数。此演算法首先会创一个只有起点的集合，接着开始逐一找出最短路径，而将最短路径会抵达的节点列入集合中，重复操作直到所有点都在集合内为止。

Dijkstra Algorithm 图解

好的～灰姑娘终於跑累了，而且玻璃鞋实在不好跑啊，於是决定之後都要开车出门不跑了！不过灰姑娘每次开车都要被收过路费，每一条路的过路费又不同，完全看当地的物价来决定，省吃俭用的灰姑娘决定好好来计算一番每个点最便宜的路线为何！省下的钱可以再买几双玻璃鞋吧！

• 首先灰姑娘先画了这张图，为了记录从家里到各点之间的价格，在不晓得能不能到达前都是无穷远，所以先将所有价格都设为无穷大，之後有比较小的数字再更新上去。
  

• 然後打开王子给的所有路径价格的地图
  

• 首先从家里 Home 出发，有两条路是 Home -> Bank 跟 Home -> Store
  

• 两条路径分别是 $150 跟 $50 ，灰姑娘记性不好所以先写下来。
  

• 从两条路线中选最便宜的一条路径 Home -> Store 画起来，确定这条路线是最佳路径，并从此路径做延伸。
  

• 於是再找出从 Store 可以延伸至其他点的所有路径，此时发现 Home -> Store -> Bank 是 $120 ( $50 + $70 ) ，比原本 Home -> Bank 的 $150 还便宜！而 Home -> Store -> Shop 是 $130 ( $50 + $80 ) ， Home -> Store -> Castle 是 $110 ( $50 + $60 ) ，
  

• 再把价格都记起来，有比较便宜就更新上去！
  

• 再选择当中最便宜的一条路，於是连接到 Castle
  

• 再从 Castle 延伸出所有可到达其他点的路径，不过 Castle -> Shop 比较贵，要 $160 ($50 + $60 + $50) ，所以不用更新原本的价格
  

• 再选择一条最便宜的路径，去 Shop 这条没有比较便宜，直接撇除！
  

• 再选择下一条比较便宜的路，连接到了 Bank
  

• 将 Bank 可延伸的所有路径标示起来，此时多一条到 Bar 的路径
  

• 因 Home -> Store -> Bank -> Bar 的价格是 $230，比无穷大还小，所以更新原本的资料
  

• 再选择下一条较便宜的路，连接到 Shop
  

• 再下一条，连接到 Bar
  

• 其他比较贵的通通撇除
  

• 好的！这就是最便宜的路线以及家里到各点的价格啦～善良的灰姑娘还把资料分给了两个姊姊跟继母呢！
  
  

Dijkstra Algorithm 时间复杂度
因戴克斯特拉演算法会使用相邻矩阵 Adjacency Matrix 的方式来执行，所以时间复杂度是 O(n^2)，若用斐波那契堆积 Fibonacci heap 可降到 O(e + log n log) 其中的 e 是指有几个边

参考资料：

Shortest Path：Intro(简介)

Youtube:最短路径演算法：Dijkstra

演算法笔记：Path

好的今天就到这边啦！感谢阅读，明天见啦掰掰！