# 圖的最短路徑
## Dijkstra 算法
適用于無負權圖的單源最短路徑問題，復雜度為 $$O(V^2+E)$$
### 最短距離
#### 偽碼
```c++
// 數組 d[] 為源點 s 到達各點的最短路徑長度
Dijkstra(G, d[], s){
初始化;
for(循環 n 次){
u=使 d[u] 最小的還未被訪問的頂點標號;
記 u 已被訪問;
for(從 u 出發所有能到達的頂點 v){
if(v 未被訪問 &&
以 u 為中介點使 s 到頂點 v 的最短距離 d[v] 更優)
優化 d[v];
}
}
}
```
#### 鄰接矩陣
```c++
const int maxv=1000;
const int inf=0x3fffffff;
int n,G[maxv][maxv];
int d[maxv];
bool vis[maxv]={false};
void Dijkstra(int s){
// 初始化
fill(d,d+maxv,inf);
d[s]=0;
for(int i=0;i<n;i++){
// 查找使 d[u] 最小的還未被訪問的頂點標號 u
int u=-1,min=inf;
for(int j=0;j<n;j++){
if(vis[j]==false && d[j]<min){
u=j;
min=d[j];
}
}
// 找不到滿足條件的 u
if(u==-1) return;
// 標記 u 已被訪問;
vis[u]=true;
// 優化 vis 集到 u 所能到達的為被訪問的頂點的距離
for(int v=0;v<n;v++){
if(vis[v]==false && G[u][v]!=inf &&
d[u]+G[u][v]<d[v])
d[v]=d[u]+G[u][v];
}
}
}
```
#### 鄰接表
```c++
const int maxv=1000;
const int inf=0x3fffffff;
int n;
int d[maxv];
bool vis[maxv]={false};
struct Node{
int v,dis;
};
vector<Node> Adj[maxv];
void Dijkstra(int s){
fill(d,d+maxv,inf);
d[s]=0;
for(int i=0;i<n;i++){
int u=-1,min=inf;
for(int j=0;j<n;j++){
if(vis[j]==false && d[j]<min){
u=j;
min=d[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
if(vis[v]==false && d[u]+Adj[u][j].dis<d[v])
d[v]=d[u]+Adj[u][j].dis;
}
}
}
```
### 最短路徑
#### 偽碼
在求最短距離偽碼的 `優化 d[v];` 之后，加上 `令 v 的前驅為 u;`
```c++
// 數組 d[] 為源點 s 到達各點的最短路徑長度
Dijkstra(G, d[], s){
初始化; // 初始化令每個節點的前驅為自身
for(循環 n 次){
u=使 d[u] 最小的還未被訪問的頂點標號;
記 u 已被訪問;
for(從 u 出發所有能到達的頂點 v){
if(v 未被訪問 &&
以 u 為中介點使 s 到頂點 v 的最短距離 d[v] 更優){
優化 d[v];
令 v 的前驅為 u; // 僅此處改動
}
}
}
}
```
#### 鄰接表
```C
#define MAXV 500
#define INF 999999
typedef int ElemType;
typedef struct
{
int no; // 頂點編號
ElemType info; // 頂點其他信息
}VertexType; // 聲明頂點類型
typedef struct
{
int edges[MAXV][MAXV]; // 鄰接矩陣
int n, e; // 定點數和邊數
VertexType vexs[MAXV]; // 存放頂點信息
}MGraph; // 聲明圖的鄰接矩陣類型
// 初始化圖的鄰接矩陣
void CreateMat(MGraph &g, int A[][MAXV], int n)
{ // 由數組 A[n][n] 生成鄰接矩陣 g
int i, j;
g.n = n;
g.e = 0;
for(i=0; i<g.n; i++){
for(j=0; j<g.n; j++){
g.edges[i][j] = A[i][j];
if(g.edges!=0)
g.e++;
}
}
}
// 迪克斯特拉算法
void Dijkstra(MGragh g, int v)
{
int dist[MAXV]; // U 集合中的各節點到 v 的最短距離
int path[MAXV]; // 用于記錄最短路徑中每一節點的前一節點
int S[MAXV]; // 已訪問集合
int mindist, i, j, u;
// 將源點歸入 S 集合，其余節點歸入 U 集合
// 初始化 U 集合中各節點到 S 集合的距離
// 將與 S 集合相連的節點的路徑中的前一節點標記為源節點
for(i=0; i<g.n; i++){
S[i] = 0;
dist[i] = g.edges[v][i];
if(g.edges[v][i]<INF)
path[i] = v;
else
path[i] = -1;
}
S[v] = 1;
for(i=0; i<g.n; i++){
// 在 U 集合中找出距離 S 集合最近的節點
mindist = INF;
for(j=0; j<g.n; j++){
if(!S[j] && dist[j]<mindist){
mindist = dist[j];
u = j;
}
}
S[u] = 1; // 將 u 點加入到 S 中
// 修改 U 集合中各節點到 v 的最短距離
for(j=0; j<g.n; j++){
if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j]){
dist[j] = dist[u] + g.edges[u][j];
path[j] = u;
}
}
}
DispAllPath(g, dist, path, S, v);
}
void DispAllPath(MGraph g, int dist[], int path[], int S[], int v)
{
int i, j, k;
int apath[MAXV], d;
for(i=0; i<g.n; i++){
if(S[i] && i!=v){
printf("The shortest path from %d to %d is %d:", v, i, dist[i]);
d = 0; apath[d] = i;
k = path[i];
if(k==-1)
printf("None\n");
else{
while(k!=v){
d++;apath[d] = path[k];
k = path[k];
}
d++; apath[d] = v;
printf("%d", apath[d]);
for(j=d-1; j>=0; j--)
printf("-->%d", apath[j]);
printf("\n");
}
}
}
}
```
### 求所有最短路徑
將 `pre[maxv]` 換成 `vector<int> pre[maxv]`
```c++
vector<int> pre[maxn];
void Dijkstra(int s){
fill(d,d+maxv,inf);
d[s]=0;
for(int i=0;i<n;i++){
int u=-1,min=inf;
for(int j=0;j<n;j++){
if(vis[j]==false && d[j]<min){
min=d[j];
u=j;
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false && G[u][v]!=inf){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
pre[v].clear();
pre[v].push_bakc(u);
}else if(d[u]+G[u][v]==d[v]){
pre[v].push_bakc(u);
}
}
}
}
}
```
### 第二標尺
第一標尺是路徑長度，有時題目還會有第二標尺。
## Bellman-Ford 算法與 SPFA 算法
復雜度為 $$O(VE)$$
### 最短距離
```c++
// 鄰接表
struct Node{
int v, dis;
};
vector<Node> Adj[maxn];
int n;
int d[maxn];
bool Bellman(int s){
fill(d,d+maxn,inf);
d[s]=0;
// 求解數組 d
for(int i=0;i<n-1;i++){
for(int u=0;u<n;u++){
for(int j=0;j<n;j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v])
d[v]=d[u]+dis;
}
}
}
// 判斷負環
for(int u=0;u<n;u++){
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v])
return false;
}
}
return true;
}
```
### 最短路徑條數
因為該算法會反復累計已經算過的頂點，設置記錄前驅的數組 `set<int> pre[maxv];` ，遇到一條與已有最短路徑長度相同的路徑時，重新計算最短路徑條數。
```c++
// ...
else if(d[u]+dis==d[v]){
pre[v].insert(u);
num[v]=0;
set<int>:: iterator it;
for(it=pre[v].begin();it!=pre[v].end();it++){
num[v]+=num[*it];
}
}
```
### SPFA (Shortest Path Faster Algorithm)
在 Bellman-Ford 算法，每次都要訪問所有邊，而實際上只有當某個頂點 u 的 d[u] 值改變時，從它出發的鄰接點 v 的 d[v] 值才會改變。對此進行優化，得到 SPFA。
#### 偽碼
```c++
queue<int> q;
源點 s 入隊;
while(q非空){
for(u 的所有鄰接邊 u->v){
if(d[u]+dis<d[v]){
d[v]=d[u]+dis;
if(v 當前不再隊列){
v 入隊;
if(v 入隊次數大于 n-1)
說明有可達負環, return;
}
}
}
}
```
#### 鄰接表
```c++
vector<Node> Adj[maxv];
int n, d[maxv],num[maxv]; // num 記錄頂點的入隊次數
bool inq[maxv];
bool SPFA(int s){
// 初始化
memset(inq,false,sizeof(inq));
memset(num,0,sizeof(num));
fill(d,d+maxv,inf);
// 源點入隊
queue<int> q;
q.push(s);
inq[s]=true;
num[s]++;
d[s]=0;
// 主體
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=false;
// 遍歷 u 的所有鄰接邊 v
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v]){
d[v]=d[u]+dis;
if(!inq[v]){
q.push(v);
inq[v]=true;
num[v]++;
if(num[v]>=n) return false;
}
}
}
}
return true;
}
```
## Floyd 算法
適用于解決全源最短路徑問題，時間復雜度為 $$O(V^3)$$
### 偽碼
```c++
枚舉頂點 k in [1,n];
以頂點為中介點，枚舉所有頂點對 i,j in [1,n]
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
```
