---
tags: 圖論
title: 最短路徑問題
---

:::success
# Dijkstra演算法

## 用途

- 求單源最短路徑 Single-Source Shortest Paths

## 理論

- 維護一個陣列，存入起點到目前讀入的每個點的最短距離
- 加入新的點時，用已維護的最短距離再經過新的邊求新的點的最短距離

## 負權圖

-

## 實作

### 用鬆弛操作實作

#### 鬆弛操作

- 將所有點的點集V分為兩個點集S和U，S中包含圖中已確定最短距離的點，U包含圖中還未確定最短距離的點

- 建立陣列d，定義d[i]為起點s到點i的最短距離，並初始化d[s]=0，d[v]=INF，其中v$\ne$s

- Greedy想法：若由結果看，將每個點與起點的距離d由小到大排序，則較大的距離可由距離較小的點再經由其他邊求得
- 第一個點為直接與起點連接的所有點中距離最近的一個
- 第二個點為直接與起點連接的所有點中第二近的==或與第一個點連接的所有點中距離最近的一個==
- 第三個點為直接與起點連接的所有點中第三近的或與第一個點連接的所有點中距離第二近的==或與第二個點連接的所有點中最近的一個==
- 依此類推，每次遞迴可遍歷所有與已求得距離的點連接的邊，通過這些邊不斷鬆弛起點到其他點的最短距離

### priority_queue偷懶法

- 用priority_queue以BFS的方式記錄目前路徑長，直接將第一次到達某點時的路徑長記為答案，可以很直觀的由小到大求最短距離，直到每個點都有答案
- 實作時比較常用
:::

:::success
# Floyd-Warshall演算法
:::

:::success
# Bellman-Ford演算法

## 用途

- 求==邊權可為負的==單源最短路徑 Single-Source Shortest Paths

## 理論

- 當圖上存在負環時，可以通過不斷

:::