# 演算法紙筆作業3 VS6102085 馬廣辰
###### tags: `NCKU`
## 第一題

Shortest path : s -> a -> d -> f -> b -> e -> c

| Step 1 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | inf | inf | inf | inf | inf | inf |

| Step 2 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | inf | inf | 4 | inf | 7 |

| Step 3 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 9 | inf | 3 | 10 | 7 |

| Step 4 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 9 | inf | 4 | 9 | 7 |

| Step 5 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 8 | 12 | 4 | 9 | 7 |

| Step 6 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 8 | 12 | 4 | 9 | 7 |

| Step 7 | s | a | b | c | d | e | f |
| ------ | --- | --- | --- | --- | --- | --- | --- |
| | 0 | 1 | 8 | 11 | 4 | 10 | 7 |

* Dijkstra’s algorithm

1. Create a shortest path set that keeps track of vertics.
1. Assign a distance value to all vertices in the input graph. Initialize all distance values as infinite.
1. While sptSet doesn’t include all vertices:
( a ) Pick a vertex u which is not in sptSet and has minimum distance.
( b ) Add u into sptSet.
( c ) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the sum of distance value of u and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

* cpp code

void shortestpath(vector<pair<int, int>> Graph[], int n, int loc){
    priority_queue<pair<int, int>> pq;
    vector<int> dist(7, INT_MAX);
    pq.push(make_pair(0, loc));
    dist[0] = 0;
    
    while(!pq.empty()){
        int u = pq.top().first;
        pq.pop();
        vector<pair<int, int>>::iterator it;
        
        for(it = Graph[u].begin();it != Graph[u].end();it ++){
            int v = (*it).first, weight = (*it).second;
            
            if(dist[v] > dist[u] + weight){
                dist[v] = dist[u] + weight;
                pq.push(make_pair(v, dist[v]));
            }
        }
    }
    
    for(int i = 0;i < n;i ++)
        cout << i << " " << dist[i] << endl;
}

void addEdge(vector<pair<int, int>> Graph[], int u, int v, int length){
    Graph[u].push_back(make_pair(v, length));
}

int main(){
    vector<pair<int, int>> Graph[7];
    addEdge(Graph, 0, 1, 1);
    addEdge(Graph, 0, 6, 7);
    addEdge(Graph, 0, 4, 4);
    addEdge(Graph, 1, 2, 8);
    addEdge(Graph, 1, 4, 2);
    addEdge(Graph, 1, 5, 9);
    addEdge(Graph, 2, 3, 5);
    addEdge(Graph, 4, 5, 6);
    addEdge(Graph, 5, 3, 2);
    addEdge(Graph, 5, 6, 3);
    addEdge(Graph, 6, 2, 1);
    addEdge(Graph, 6, 3, 5);
    shortestpath(Graph, 7, 0);
}

## 第二題

**Answer**

| | 0 | 1 | 2 | 3 |
| --- | --- | --- | --- | --- |
| 0 | 0 | 5 | 8 | 6 |
| 1 | 6 | 0 | 3 | 4 |
| 2 | 3 | 8 | 0 | 1 |
| 3 | 2 | 7 | 10 | 0 |

* Floyd Warshall Algorithm

1. Initialize the solution matrix same as the input graph as a first step.
2. Update the solution matrix by considering all vertices as an intermediate vertex. One by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path.
For every $pair (i, j)$ of the source and destination vertices respectively, there are two possible cases.
* k is not an intermediate vertex in shortest path from $i$ to $j$. We keep the value of $dist[i][j]$ as it is.
* k is an intermediate vertex in shortest path from $i$ to $j$. We update the value of $dist[i][j]$ as $dist[i][k] + dist[k][j]$ if $dist[i][j] > dist[i][k] + dist[k][j]$

* cpp code

void floyd_warshall(vector<vector<int>> &Graph, int n){
    int dist[4][4];
    for(int i = 0;i < 4;i ++){
        for(int j = 0;j < 4;j ++)
            dist[i][j] = Graph[i][j];
    }
    
    for(int k = 0;k < 4;k ++){
        for(int i = 0;i < 4;i ++){
            for(int j = 0;j < 4;j ++){
                if(dist[i][j] > dist[i][k] + dist[k][j] && dist[k][j] != INT_MAX && dist[i][k] != INT_MAX)
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    
    for(int i = 0;i < 4;i ++){
        for(int j = 0;j < 4;j ++){
            if(dist[i][j] == INT_MAX)
                cout << "INF" << "    ";
            else
                cout << dist[i][j] << "    ";
        }
        
        cout << endl;
    }
}

int main(){
    vector<vector<int>> Graph;
    Graph.push_back({0, 5, INT_MAX, 6});
    Graph.push_back({7, 0, 3, INT_MAX});
    Graph.push_back({14, INT_MAX, 0, 1});
    Graph.push_back({2, INT_MAX, INT_MAX, 0});
    floyd_warshall(Graph, 4);
}

## 第三題
**Answer**

* Bellman Ford Algorithm
1. Initializes distances from the source to all vertices as infinite and distance to the source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
2. Calculates shortest distances. Do following |V|-1 times.
dist[v] > dist[u] + weight of edge uv, then dist[v] = dist[u] + weight of edge uv.
3. Check whether there is a negative cycle.

* cpp code

void DFS(vector<pair<int, int>> Graph[], vector<int> &dist, vector<int> &predecessor, vector<bool> &visit, int j){
    visit[j] = true;
    vector<pair<int, int>>::iterator it;
    
    for(it = Graph[j].begin();it != Graph[j].end();it ++){
        if(dist[j] + (*it).second < dist[(*it).first]){
            dist[(*it).first] = dist[j] + (*it).second;
            predecessor[(*it).second] = j;
        }
    }
}

void findPath(vector<pair<int, int>> Graph[], int v, int e){
    vector<int> dist(v, 150), predecessor(v, -1);
    dist[0] = 0;
    
    for(int i = 0;i < v -1;i ++){
        vector<bool> visit(v, false);
        for(int j = 0;j < v;j ++){
            if(!visit[j])
                DFS(Graph, dist, predecessor, visit, j);
        }
    }
    
    vector<pair<int, int>>::iterator it;
    
    for(int i = 0;i < v;i ++){
        for(it = Graph[i].begin();it != Graph[i].end();it ++)
            if(dist[i] + (*it).second < dist[(*it).first]){
                cout << "No solution";
                return;
            }
    }
    
    for(int i = 0;i < v;i ++)
        cout << i << " " << dist[i] << endl;
}

void addEdge(vector<pair<int, int>> Graph[], int v, int u, int weight){
    Graph[v].push_back(make_pair(u, weight));
}

int main(){
    vector<pair<int, int>> Graph[5];
    addEdge(Graph, 2, 0, 1);
    addEdge(Graph, 2, 1, -4);
    addEdge(Graph, 4, 3, 2);
    addEdge(Graph, 3, 2, 7);
    addEdge(Graph, 0, 4, 5);
    addEdge(Graph, 1, 3, 10);
    addEdge(Graph, 1, 0, 2);
    addEdge(Graph, 2, 4, -1);
    findPath(Graph, 5, 8);
}