Floyd_Warshall implementation

矩陣輸入
#include <stdio.h>
#include <limits.h>
#include <vector>

using namespace std;

void Floyd_Warshall(vector<vector<int> > &graph, vector<vector<int> > &shortest)
{
    int none = -1;
    int n = graph.size();
    if (n == 0) {
        return;
    }
    if (shortest.size() != n) {
        return;
    }
    for (int i = 0; i < n; i++) {
        if ((shortest[i].size()) != n || (graph[i].size() != n))
            return;
    }

    // initialize shortest
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] >= 0) {
                shortest[i][j] = graph[i][j];
            } else {
                shortest[i][j] = INT_MAX;
            }
        }
    }

    for (int maxHalfway = 0; maxHalfway < n; maxHalfway++) {
        for (int source = 0; source < n; source++) {
            for (int dist = 0; dist < n; dist++) {
                if (shortest[source][maxHalfway] != INT_MAX && shortest[maxHalfway][dist] != INT_MAX) {
                    if (shortest[source][dist] > (shortest[source][maxHalfway] + shortest[maxHalfway][dist])) {
                        shortest[source][dist] = (shortest[source][maxHalfway] + shortest[maxHalfway][dist]);  
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (shortest[i][j] != INT_MAX)
                printf("%2d  ", shortest[i][j]);
            else
                printf("%2d  ", none);
        }
        printf("\n");
    }

}


// driver program to test above function
int main()
{
   /* Let us create the example graph discussed above */
   int input[9][9] = {{ 0,  4, -1, -1, -1, -1, -1,  8, -1},
                      { 4,  0,  8, -1, -1, -1, -1, 11, -1},
                      {-1,  8,  0,  7, -1,  4, -1, -1,  2},
                      {-1, -1,  7,  0,  9, 14, -1, -1, -1},
                      {-1, -1, -1,  9,  0, 10, -1, -1, -1},
                      {-1, -1,  4, 14, 10,  0,  2, -1, -1},
                      {-1, -1, -1, -1, -1,  2,  0,  1,  6},
                      { 8, 11, -1, -1, -1, -1,  1,  0,  7},
                      {-1, -1,  2, -1, -1, -1,  6,  7,  0}
                     };

    vector<vector<int> > graph;
    vector<vector<int> > result;
    for (int i = 0; i < 9; i++) {
        vector<int> now(9, 0);
        result.push_back(now);
        for (int j = 0; j < 9; j++) {
            now[j] = input[i][j];
        }
        graph.push_back(now);
    }

    Floyd_Warshall(graph, result);
    printf("end\n");
    return 0;
}

邊輸入
#include <stdio.h>
#include <limits.h>
#include <vector>

using namespace std;

void Floyd_Warshall(vector<vector<pair<int, int> > > &edges, vector<vector<int> > &shortest)
{
    int none = -1;
    int n = edges.size();
    if (n == 0) {
        return;
    }
    if (shortest.size() != n) {
        return;
    }
    for (int i = 0; i < n; i++) {
        if ((shortest[i].size()) != n)
            return;
    }

    // initialize shortest
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                shortest[i][j] = 0;
            } else {
                shortest[i][j] = INT_MAX;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < edges[i].size(); j++) {
            shortest[i][edges[i][j].first] = edges[i][j].second;
        }
    }

    for (int maxHalfway = 0; maxHalfway < n; maxHalfway++) {
        for (int source = 0; source < n; source++) {
            for (int dist = 0; dist < n; dist++) {
                if (shortest[source][maxHalfway] != INT_MAX && shortest[maxHalfway][dist] != INT_MAX) {
                    if (shortest[source][dist] > (shortest[source][maxHalfway] + shortest[maxHalfway][dist])) {
                        shortest[source][dist] = (shortest[source][maxHalfway] + shortest[maxHalfway][dist]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (shortest[i][j] != INT_MAX)
                printf("%2d  ", shortest[i][j]);
            else
                printf("%2d  ", none);
        }
        printf("\n");
    }

}


// driver program to test above function
int main()
{
   /* Let us create the example graph discussed above */
   int input[9][9] = {{ 0,  4, -1, -1, -1, -1, -1,  8, -1},
                      { 4,  0,  8, -1, -1, -1, -1, 11, -1},
                      {-1,  8,  0,  7, -1,  4, -1, -1,  2},
                      {-1, -1,  7,  0,  9, 14, -1, -1, -1},
                      {-1, -1, -1,  9,  0, 10, -1, -1, -1},
                      {-1, -1,  4, 14, 10,  0,  2, -1, -1},
                      {-1, -1, -1, -1, -1,  2,  0,  1,  6},
                      { 8, 11, -1, -1, -1, -1,  1,  0,  7},
                      {-1, -1,  2, -1, -1, -1,  6,  7,  0}
                     };

    vector<vector<pair<int, int> > > edges;
    vector<vector<int> > result;

    for (int i = 0; i < 9; i++) {
        vector<pair<int, int> > connect;
        vector<int> temp(9, 0);
        result.push_back(temp);
        for (int j = 0; j < 9; j++) {
            if (input[i][j] > 0) {
                connect.push_back(make_pair(j, input[i][j]));
            }
        }
        edges.push_back(connect);
    }

    Floyd_Warshall(edges, result);
    printf("end\n");
    return 0;
}

留言

張貼留言

這個網誌中的熱門文章

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/longest-univalue-path/

[Implementation idea]: It is the same as longest path of a tree but with limitation. http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ For Diameter of a Binary Tree, we need to recursively find out the height H() of sub-tree rooted at left & right child for each node. Then the answer is the node with max(H(node->left) + H(node->right)) + 1. For this case, an additional limit is the definition  height H'().  It needs to be the same value to it's left or right child now.   If not so, H'(node) is 0. Recursively calculate H'() for each node within the target tree. The answer is max(H'(node->left) + H'(node->right)) + 1 . #include <iostream> #include <set> #include <vector> #include <unordered_map> #include <limits.h> using namespace std; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(i...
閱讀完整內容

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/maximum-sum-of-3-non-overlapping-subarrays/

圖片
[Implementation idea]: [Native way] A native way is to check all triple candidates, filter out illegals and find the one the maximum sum. Complexity is O(n^3). [Better way] Apply dynamic programming. Complexity is O(nlogn) Complexity is O(n) Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Assume A(i, j) represents the maximum j Non-Overlapping Sub-arrays sum whose last  chosen index is at position i. A(i, 1) = 1. sum(A(k)) k = i, i-1, ... i-k+1, if i  >= (k - 1). 2. 0, otherwise. A(i, 2) = 1. A(i, 1) + max(A(i-k, 1)); if i  >= (2*k - 1).  2. 0, otherwise. A(i, 3) = 1. A(i, 1) + max(A(i-k, 2)); if i  >= (3*k - 1).  2. 0, otherwise. Formula A(i,1) is intuitive; Formula A(i,2) comes from the fact that - we must ended ...
閱讀完整內容