# 4/13 科培第九次社課

## 目錄
[TOC]

---
## 一點點圖論
### 概念
* 濫觴：七橋問題
* 把圖簡化成點和邊

### 類別
* 有向圖v.s.無向圖
* 權重

### 怎麼表示一個圖呢？
**先來個圖舉例**

**我是陣列：** 1表示有連通，0表示沒有連通( / ∞ )
| X | 0 | 1 | 2 | 3 | 4 |
| - | - | - | - | - | - |
| **0** | 0 | 1 | 1 | 0 | 0 |
| **1** | 1 | 0 | 1 | 1 | 0 |
| **2** | 1 | 1 | 0 | 1 | 0 |
| **3** | 0 | 1 | 1 | 0 | 1 |
| **4** | 0 | 0 | 0 | 1 | 0 |

**矩陣v.s.串列**
:::info
**鄰接矩陣**：簡單方便易上手，缺點是效率低（你會開一個很巨大的陣列）
**鄰接串列**：效率比較高，常用 vector 或 linked-list 實作
:::

---
## 最短路徑
### 概念
當我們想要求出兩地點之間的最短距離時，就需要特定的演算法幫我們求出來。

**這次我們加入邊長來看**

### **Dijkstra**：單點到所有點的最短路徑
*~ 一種greedy的演算法*

**我們先畫個表格（以1為起點）**
自己到自己視為0
| 回合 | 1 | 2 | 3 | 4 | 5 |
| - | - | - | - | - | - |
| 0 | 0 | 2 | 5 | X | X |
| 1 | 0 | 2 | <font color="#f00">3</font> | 6 (7) | X |
| 2 | 0 | 2 | 3 | <font color="#f00">5</font> | 12 (13) |
| 3 | 0 | 2 | 3 | 5 | <font color="#f00">11</font> |

* 不能有負權

### 1. 陣列版
* AP325 261
:::spoiler <font color="#00FF25">我的第一個dijkstra程式</font>

#include <iostream>
using namespace std;

//graph, distance,findornot
int G[101][101], D[101], V[101], n;

int main()
{
    int m, i, j, k, a, b, l;
   	cin >> n >> m;
   	//initialize
   	for (i=1; i<=n; i++)
   	    for (j=1; j<=n; j++)
   	    {
   	    	if (i==j) G[i][j]=0;//self-self
   	        else G[i][j]=1000000000;
   	    }
   	for (i=0; i<m; i++)
   	{
   		cin >> a >> b >> l;//node-node
   		G[a][b]=l;
   		G[b][a]=l;
   	}
   	//dijkstra
    for (i=0; i<=n; i++) D[i]=1000000000, V[i]=0;
    D[1]=0;//start from 1
    while (1)
    {
    	for (i=1, k=0; i<=n; i++){
            if (V[i]==0 && D[i]<D[k]) k=i;//有連通但還沒找完
    	}
    	if (k==0) break;

	V[k]=1;
    	for (i=1; i<=n; i++)
    	{
    		if (D[k]+G[k][i]<D[i]) D[i]=D[k]+G[k][i];
    	}
    }
    cout<< "start from node 1"<<'\n';
    for (i=1; i<=n; i++)
        cout << "1->"<< i << " : " << D[i] << "\n";
    return 0;
}

:::

### 2. priority_queue版
**priority_queue介紹**

* vector 或 deque 變形，預設是最大的優先取出
* 功能、語法介紹 https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji/stl/priority

**進入正題**
* AP325 262 263
https://drive.google.com/file/d/1hX7q3wVKkLuoMhEEm7uuLjq4BuhZAEgn/view?usp=sharing

https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/tu-xing-zui-duan-lu-jing

:::spoiler <font color="#00FF25">PQ版本dijkstra</font>

#include <iostream>
#include <queue>
#include <cstring>
#include <deque>
using namespace std;
//struct
struct Edge{
  int from,to;
  int w;
  bool operator<(const Edge &rhs) const{
    return (rhs.w < w);
  }
};
deque<Edge> G[100];
bool v[100];
int dis[100];
int main(){
  int n,m,a,b,w;
  priority_queue<Edge> pq;
  Edge tmp,pqedge;
  cin >> n >> m;
  for(int i=0;i<n;i++){
    G[i].clear();
  }
  for(int i=0;i<m;i++){
    cin >> a >> b >> w;
    tmp.from=a;
    tmp.to=b;
    tmp.w=w;
    G[a].push_back(tmp);
    tmp.from=b;
    tmp.to=a;
    tmp.w=w;
    G[b].push_back(tmp);
  }
  memset(v,0,sizeof(v));
  memset(dis,0x6f,sizeof(dis));
  pqedge.from=0;
  pqedge.w=0;
  dis[0]=0;
  pq.push(pqedge);
  while(!pq.empty()){
    pqedge=pq.top();
    pq.pop();
    int from=pqedge.from;
    if (v[from]==0){
      v[from]=1;
      for(int i=0;i<G[from].size();i++){
        if (v[G[from][i].to]==0){
          if (dis[G[from][i].to]>dis[from]+G[from][i].w) {
            dis[G[from][i].to]=dis[from]+G[from][i].w;
            tmp.from=G[from][i].to;
            tmp.w=dis[G[from][i].to];
            pq.push(tmp);
          }
        }
      }
    }
  }
  for(int i=0;i<n;i++){
    cout << dis[i]<<" ";
  }
  cout << endl;
}

:::

### **Floyd-Warshall**：所有點之間的最短路徑
*~ 一種DP的演算法*
* 主要想法 https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/tu-xing-zui-duan-lu-jing

#### 陣列版
:::spoiler <font color="#00FF25">我的第一個floyd-warshall程式</font>

#include <iostream>
using namespace std;

int G[101][101], n;

int main()
{
    int m, i, j, k, a, b, l;
   	cin >> n >> m;
    //initialize
   	for (i=1; i<=n; i++)
   	    for (j=1; j<=n; j++)
   	    {
   	    	if (i==j) G[i][j]=0;
   	        else G[i][j]=1000000000;
   	    }
   	for (i=0; i<m; i++)
   	{
   		cin >> a >> b >> l;
   		G[a][b]=l;
   		G[b][a]=l;
   	}
   	//floydwarshall
    for (k=1; k<=n; k++)
    {
    	for (i=1; i<=n; i++)
    	{
    		if (G[i][k]==1000000000) continue;
    		for (j=1; j<=n; j++)
    		{
    			if (G[i][k]+G[k][j]<G[i][j]) G[i][j]=G[i][k]+G[k][j];//important!
    		}
    	}
    }
    for (i=1; i<=n; i++)
    {
    	for (j=1; j<=n; j++)
    	{
    		cout << G[i][j] << " ";
    	}
    	cout << endl;
    }
    return 0;
}

:::
---

### 實作環節（from AP325）

---
## 練習資源
### Dijkstra
**ZJ d793 Number Maze**
https://zerojudge.tw/ShowProblem?problemid=d793

### Floyd-Warshall
**ZJ c125 Frogger**（座標）
https://zerojudge.tw/ShowProblem?problemid=c125
**ZJ c128 Heavy Cargo**（需處理字串）
https://zerojudge.tw/ShowProblem?problemid=c128
**ZJ d282 11015 - 05-2 Rendezvous**（需處理字串）
https://zerojudge.tw/ShowProblem?problemid=d282

### Reference
**ZJ APCS 蓋步道（實作第4題）**
https://zerojudge.tw/ShowProblem?problemid=j125
**Yui Huang題目單** https://yuihuang.com/oj-level-4

---
## 參考資料
* 黃建庭老師教學網站
演算法一 https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji?authuser=0
演算法二 https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji-2?authuser=0
* 吳邦一教授AP325講義 https://drive.google.com/file/d/1hX7q3wVKkLuoMhEEm7uuLjq4BuhZAEgn/view?usp=sharing
* CSES book.pdf(只有英文版) https://cses.fi/book/book.pdf
* 旭喨老師的培訓教材
* APCSC教材