[High-order data structure] Union search of sets and graphs

Table of Contents

1. Data structure – Union search

2. Data structure–Fig.

1. Basic concepts of graphs

2. Simple implementation of the graph

2.1. Graph implementation of adjacency matrix

2.2. Graph implementation of adjacency list

2.3. DFS and BFS of graphs

2.4. Minimum spanning tree

2.4.1.Kruskal (Kruskal algorithm)

2.4.2.Prim (Prim’s algorithm)

2.5.Shortest path

2.5.1.Dijkstra (Dijkstra algorithm)

2.5.2.Bellman-Ford (Bellman-Ford algorithm)

2.5.3.Floyd-Warshall (Floyd algorithm)

1. Data structure–Union-find

Concept: Dividen different elements into some disjoint sets.

1. At the beginning,each element forms its own single-element collection; initialization
2. Then combine the sets belonging to the same group of elements according to certain rules; merge
3. In this process, the operation of querying which set a certain element belongs to is repeatedly used: Query The abstract data type suitable for describing this type of problem is called union-find set (union-find set)

Concept map:

Implementation: Count: There are as many sets as there are negative numbers in traversing array elements.

#pragma once
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

template<class T>
class UnionFindSet {
public:
int Find(T val)
{
int index = _find_index[val];
while (_v[index] >= 0)
index = _v[index];
return index;
}
bool Union(T x, T y)
{
int xi = Find(x);
int yi = Find(y);
//Whether it has been combined
if (xi == yi)
return false;
_v[xi] + = _v[yi];
_v[yi] = xi;
return true;
}
//How many collections are there?
intCount()
{
int count = 0;
for (auto e : _v)
{
if (e < 0)
count + + ;
}
return count;
}
public:
UnionFindSet(const vector<T> & amp; tmp)
{
for (int i = 0; i < tmp.size(); i + + )
_find_index[tmp[i]] = i;
_v.resize(tmp.size(), -1);
}
~UnionFindSet()
{}
private:
//
vector<T> _v;
//Data and subscripts of hash array
unordered_map<T, int> _find_index;
};

test:

#include<iostream>
#include"UnionFindSet.h"
#include<string>

using namespace std;

int main()
{
vector<int> v{ 1,23,432,5345,8,712,44,534,645,73,862,3};
UnionFindSet<int> ufs(v);

ufs.Union(1, 534);
ufs.Union(1, 534);
ufs.Union(73, 534);
ufs.Union(1, 4);
ufs.Union(23, 8);
ufs.Union(862, 73);
ufs.Union(3,3);
cout << ufs.Count() << endl;
return 0;
}

You can try this question: use union search to do

Leetcode: number of provinces

class UnionFindSet{
    public:
    int Find(int x)
    {
        //find subscript
        int index = _find_index[x];
        while(_v[index] >= 0)
        {
            index = _v[index];
        }
        return index;
    }

    bool Union(int x, int y)
    {
        int xi = Find(x);
        int yi = Find(y);
        //already combined
        if(xi == yi)
            return false;
        _v[xi] + = _v[yi];
        _v[yi] = xi;
        return true;
    }
    intCount()
    {
        int count = 0;
        for(auto e : _v)
        {
            if(e < 0)
                count + + ;
        }
        return count;
    }
    public:
    UnionFindSet(const vector<int> & amp; v)
    {
        _v.resize(v.size(), -1);
        for(int i = 0; i<v.size();i + + )
            _find_index[i] = i;
    }
    private:
    vector<int> _v;
    unordered_map<int, int> _find_index;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>> & amp; isConnected) {
        int n = isConnected.size();
        vector<int> v;
        for(int i =0; i<n; i + + )
        {
            v.push_back(i);
        }
        UnionFindSet ufs(v);
        for(int i = 0; i<n; i + + )
        {
            for(int j=0; j<n; j + + )
            {
                if(isConnected[i][j] == 1)
                {
                    ufs.Union(i,j);
                }
            }
        }
        return ufs.Count();
    }
};

2. Data structure–Figure

1. Basic concepts of graphs

Graph: consists of a vertex set and the relationship between vertices (edge), that is, G = (V, E);

1. Vertex: any vertex in the graph;
2. Edge: connects two vertices;
3. Edge weight: the value of the edge connecting two vertices;

Undirected graphs and directed graphs

1. Undirected graph: The edge between two vertices has no direction, and the weight of the two edges is represented by a numerical value; so it is a strong relationship graph: for example: QQ and WeChat are friends with each other
2. Directed graph: The edge between two vertices has a direction, which represents the weight from one vertex to another; so it is a weak relationship graph: for example, if Douyin follows the anchor, the anchor will not follow you at the same time strong>

Complete graph: In an undirected graph with n vertices, if there are n * (n-1)/2 edges, that is, there is only one between any two vertices. edge, then this graph is called an undirected complete graph, such as the above graph G1;In a directed graph with n vertices, if there are n * (n-1) If there are edges between any two vertices and there are only edges with opposite directions, then the graph is called a directed complete graph, such as the above graph G4.

Degree of vertex: The degree of vertex v refers to the number of edges associated with it, denoted as deg(v); Ina directed graph, the degree of a vertex is equal to the sum of the in-degree and out-degree of the vertex, where the in-degree of vertex v is the number of directed edges ending with v, denoted as indev (v); The out-degree of vertex v is the number of directed edges starting from v, which is recorded as outdev(v). Therefore:dev(v) = indev(v) + outdev(v). Note: For anundirected graph, the degree of a vertex is equal to the in-degree and out-degree of the vertex, i.e. dev(v) = indev(v) = outdev(v).

Simple paths and loops: If the vertices v1, v2, v3, …, vm on the path do not repeat (a path that does not constitute a loop), then such a path is called a simple path strong>. If thefirst vertex v1 and the last vertex vm on the path coincide, then such a path is called a loop or ring.

Spanning tree: The smallest connected subgraph of a connected graph (the entire graph is connected, and any vertex can find another vertex) is called the spanning tree of the graph. The spanning tree of a connected graph with n vertices has n vertices and n-1 edges.

2. Simple implementation of graph

2.1. Graph implementation of adjacency matrix

Advantages: Using the adjacency matrix can quickly find (time complexity O(1)) whether two vertices have an edge and the weight of the edge; Disadvantage: finding the degree of a vertex (time complexity O(N));

Design concept: With n vertices, create an n*n two-dimensional matrix to place the weights of the two vertex edges. If it is empty, you can use the maximum or minimum value of a weight;

#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include"UnionFindSet.h"

using namespace std;

//V vertex type, W weight type
namespace Matrix {
template<class V, class W, bool Direction = false, W W_MAX = INT_MAX>
class Graph {
public:
typedef Graph<V, W, Direction, W_MAX> Self;
int Find(const V & amp; v)
{
auto it = _find_index.find(v);
if (it == _find_index.end())
return -1;
return it->second;
}
bool AddEdge(const V & amp; src, const V & amp; des, const W & amp; weight)
{
int si = Find(src);
int di = Find(des);
//wrong vertex
if (si == -1 || di == -1)
return false;
_matrix[si][di] = weight;
if (Direction == false)
_matrix[di][si] = weight;
return true;
}
void Print()
{
for (int i = 0; i < _matrix.size(); i + + )
{
for (int j = 0; j < _matrix.size(); j + + )
{
if (_matrix[i][j] == W_MAX)
printf("", '*');
else
printf("]", _matrix[i][j]);
}
cout << endl;
}
}
public:
Graph(const vector<V> & amp; v)
{
int n = v.size();
_vertexs.resize(n);
//Initialize the vertex collection and the mapping of vertices and subscripts
for (int i = 0; i < n; i + + )
{
_vertexs[i] = v[i];
_find_index[v[i]] = i;
}
//Initial adjacency matrix
_matrix.resize(n, vector<W>(n, W_MAX));
}
Graph() = default;
~Graph()
{}
private:
//vertex collection
vector<V> _vertexs;
//Find the vertex subscript
unordered_map<V, int> _find_index;
vector<vector<W>> _matrix;

};
}
void test()
{
    vector<string> a{ "Zhang San", "Li Si", "Wang Wu", "Zhao Liu", "Zhou Qi" };
    Matrix::Graph<string, int, false> g1(a);
    g1.AddEdge("Zhang San", "Li Si", 100);
    g1.AddEdge("Zhang San", "Wang Wu", 200);
    g1.AddEdge("王五", "Zhao Liu", 30);
    g1.AddEdge("王五", "weekday", 30);
    g1.Print();

    g1.Print();
}
int main()
{
    test();
    return 0;
}

2.2. Graph implementation of adjacency list

Advantages: When looking up the degree of a vertex (the time complexity is O(1), add a count), it saves space; Disadvantages: Use the adjacency list to find whether two vertices have an edge and the weight of the edge (worst case : time complexity O(N)), low insertion efficiency: need to traverse the linked list to see if it already exists

Design concept: There are n vertices, create a pointer matrix with n elements, insert a new edge and traverse the linked list to see if it exists;

namespace List {
template<class W>
class Node {
public:
int _des;
//weight
W _weight;
Node<W>* _next;
Node(int des, W w):_des(des),_weight(w),_next(nullptr)
{}
};
template<class V, class W, bool Direction = false>
class Graph{
public:
int Find(const V & amp; v)
{
auto it = _find_index.find(v);
if (it == _find_index.end())
return -1;
return it->second;
}
bool AddEdge(const V & amp; src, const V & amp; des, const W & amp; weight)
{
//Get the subscript
int si = Find(src);
int di = Find(des);
//Element does not exist, fail;
if (si == -1 || di == -1)
return false;
//Add edge to adjacency list
//Whether the array pointer is nullptr
if (_table[si] == nullptr){
//Create object
Node<W>* new_node = new Node<W>(di, weight);
new_node->_next = _table[si];
_table[si] = new_node;
\t\t\t\t//Undirected graph
if (Direction == false) {
Node<W>* new_node = new Node<W>(si, weight);
new_node->_next = _table[di];
_table[di] = new_node;
}

}
else {//Need to compare with the elements in the adjacency list to see if they have been added
Node<W>* nd = _table[si];
while(nd)
{
if (nd->_des == di)
return false;
else
nd = nd->_next;
}
//Not added yet
Node<W>* new_node = new Node<W>(di, weight);
new_node->_next = _table[si];
_table[si] = new_node;
\t\t\t\t//Undirected graph
if (Direction == false) {
Node<W>* new_node = new Node<W>(si, weight);
new_node->_next = _table[di];
_table[di] = new_node;
}
}
return true;

}
void Print()
{
for (int i = 0; i < _table.size(); i + + )
{
cout << _vertexs[i] << ": ";
Node<W>* nd = _table[i];
while(nd)
{
cout << _vertexs[nd->_des] << " " << nd->_weight << " ";
nd = nd->_next;
}
cout << endl;
}
}
public:
Graph(const vector<V> & amp; v)
{
int n = v.size();
_vertexs.reserve(n);
for (int i = 0; i < n; i + + )
{
_vertexs.push_back(v[i]);
_find_index[v[i]] = i;
}
_table.resize(n, nullptr);
}
private:
//vertex collection
vector<V> _vertexs;
//Hash of vertices and subscripts
unordered_map<V, int> _find_index;
//adjacency list
vector<Node<W>*> _table;
};
}
void test()
{
    vector<string> a{ "Zhang San", "Li Si", "Wang Wu", "Zhao Liu", "Zhou Qi" };
    List::Graph<string, int, false> g1(a);
    g1.AddEdge("Zhang San", "Li Si", 100);
    g1.AddEdge("Zhang San", "Wang Wu", 200);
    g1.AddEdge("王五", "Zhao Liu", 30);
    g1.AddEdge("王五", "weekday", 30);
    g1.Print();

    g1.Print();
}
int main()
{
    test();
    return 0;
}

2.3. DFS and BFS of graphs

I use an adjacency list graph to implement it. The adjacency matrix is similar. Just insert the code into the List::graph class and you can use it;

 void _DFS(int pos, vector<bool> & amp; visited)
{
visited[pos] = true;
Node<W>* nd = _table[pos];
while(nd)
{
cout << _vertexs[pos] << _vertexs[nd->_des] << " ";
if (visited[nd->_des] == false)
_DFS(nd->_des, visited);
nd = nd->_next;
}
}
void DFS(const V & amp; v)
{
int pos = _find_index[v];
vector<bool> visited(_table.size(), false);
_DFS(pos, visited);

}
void BFS(const V & v)
{
int pos = _find_index[v];
vector<bool> visited(_table.size(), false);
queue<int> q;
q.push(pos);
while (!q.empty())
{
int size = q.size();
while (size--)
{
pos = q.front();
visited[pos] = true;
q.pop();
Node<W>* nd = _table[pos];
while(nd)
{
cout << _vertexs[pos] << _vertexs[nd->_des] << " ";
if (visited[nd->_des] == false)
q.push(nd->_des);
nd = nd->_next;
}
\t\t\t\t\t
}
}
}

2.4. Minimum spanning tree

The subsequent five algorithms all use the Matrix::Graph class

Minimum spanning trees usually use undirected graphs;

• Minimum spanning tree: There are n vertices, use n-1 edges, and use all vertices to connect, then it definitely does not form a loop (it is impossible to form a loop with all connections);

2.4.1.Kruskal(Kruskal algorithm)

Greedy thoughts:

1. Add all edges to the priority queue;
2. Take out the top edge of the heap (the smallest) and use the union search to determine whether it forms a loop;
3. Each edge has two vertices. Use union-find to merge the two vertices of the edge;
4. Maybe the minimum spanning tree cannot be formed, so the end condition is that the priority queue is not empty;
5. Use a variable to record how many edges there are, and the last n-1 is the minimum spanning tree;

And find the code: at the top

 //Greedy thinking, select the edge with the smallest weight, and use the union set to determine whether it forms a loop.
W Kruskal(Self & minTree)
{
//Initialize spanning tree
int n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._find_index = _find_index;
minTree._matrix.resize(n, vector<W>(n, W_MAX) );

//Priority queue saves edges
priority_queue<Edge<W>, vector<Edge<W>>, greater<Edge<W>>> pq;

//Add all edge entry priority queues
for (int i = 0; i < n; i + + )
{
for (int j = i + 1; j < n; j + + )
{
if (_matrix[i][j] != W_MAX)
pq.push(Edge<W> (i, j, _matrix[i][j]) );
}
}

//There are n-1 edges
int count = 0;
UnionFindSet<V> ufs(_vertexs);
int totalW = 0;
while (!pq.empty())
{
Edge<W> eg= pq.top();
pq.pop();
bool ret = ufs.Union(_vertexs[eg._src], _vertexs[eg._des]);
if (ret == true){//Does not constitute a loop
cout << _vertexs[eg._src] << ' ' << _vertexs[eg._des] << ' ' << eg._weight << endl;
minTree.AddEdge(_vertexs[eg._src], _vertexs[eg._des], eg._weight);
count + + ;
totalW + = eg._weight;
}
else {//
cout << "Constituting a ring " << _vertexs[eg._src] << ' ' << _vertexs[eg._des] << ' ' << eg._weight << endl;
}
//The total weight of the composition
}
if (count == n - 1)//can form a spanning tree
return totalW;
else//cannot be formed
return W();
}

Test code:

void TestGraphMinTree()
{
const char* ch = "abcdefghi";
vector<char> v;
for (int i = 0; i < strlen(ch); i + + )
{
v.push_back(ch[i]);
}
Matrix::Graph<char, int> g(v);
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);

Matrix::Graph<char, int> kminTree;
cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
kminTree.Print();
}

2.4.2.Prim (Prim’s algorithm)

Greedy thoughts:

1. Determine a vertex, add all edges of this vertex to the priority queue, and this vertex is set to used;
2. Take out the edge at the top of the heap and see if the two vertices have been used. Used represents a ring;
3. Insert all edges of this vertex into the priority queue without forming a ring, and this vertex is set to used;
4. Repeat this process, I use a hash table to determine the vertices, it would be better to use a bool array;
5. Use a variable to record how many edges there are, and the last n-1 is the minimum spanning tree;

 //Greedy thinking, extend according to the selected point, use set to save the used ones, if you don’t use the used ones, you will definitely not construct the ring.
//The union search is not used because the used nodes are all connected.
W Prim(Self & amp;minTree, const V & amp; val)
{
int n = _vertexs.size();
//Initialize mintree
minTree._vertexs = _vertexs;
minTree._find_index = _find_index;
minTree._matrix.resize(n, vector<W>(n, W_MAX));
\t\t\t
int pos = _find_index[val];
//Save used
unordered_set<V> visited;
visited.insert(pos);

priority_queue<Edge<W>, vector<Edge<W>>, greater<Edge<W>> > pq;//
for (int j = 0; j < n; j + + ) {
if(_matrix[pos][j] != W_MAX)
pq.push(Edge<W>(pos, j, _matrix[pos][j]));
}
int count = 0;//Number of edges
W TotalW = 0;//weight size
while (!pq.empty())
{
//Get the current minimum
Edge<W> dg = pq.top();
pq.pop();
int des = dg._des;
if(visited.count(des))//Exists, not available
cout << "Constituting a ring " << _vertexs[dg._src] << ' ' << _vertexs[dg._des] << ' ' << dg._weight << endl;
else {
for (int j = 0; j < n; j + + )//Add new edge
{
if(_matrix[des][j] != W_MAX)
pq.push(Edge<W>(des, j, _matrix[des][j]));
}
visited.insert(des); //Already used
minTree._matrix[dg._src][dg._des] = dg._weight;//Add edges to spanning tree
TotalW + = dg._weight;
count + + ;
cout << _vertexs[dg._src] << ' ' << _vertexs[dg._des] << ' ' << dg._weight << endl;
}


}
if (count == n - 1)
return TotalW;
else
return W();
}

Test code:

void TestGraphMinTree()
{
const char* ch = "abcdefghi";
vector<char> v;
for (int i = 0; i < strlen(ch); i + + )
{
v.push_back(ch[i]);
}
Matrix::Graph<char, int> g(v);
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);

Matrix::Graph<char, int> kminTree;
cout << "Prim:" << g.Prim(kminTree, 'a') << endl;
kminTree.Print();
}

2.5. Shortest path

The shortest paths usually use directed graphs;

2.5.1.Dijkstra(Dijkstra algorithm)

Greedy thinking: Disadvantages of this algorithm: It can only be used for graphs without negative weight (negative weight means less than 0), because it is determined that it does not have negative weight. The path value cannot be smaller (a number plus a positive number cannot be smaller); advantage: best performance (time: O(N^2), adjacency matrix)

1. Based on the incoming vertex, set this path value to 0;
2. Traverse to find the unused vertex with the smallest path value, and set the vertex as used
3. Traverse all the edges of this min vertex. If the path value of this min vertex + the value of this edge
4. Loop this process;

void Dijkstra(const V & amp; v, vector<W> & amp; dest, vector<int> & amp; parentPath )
{
int n = _vertexs.size();
//Start point subscript
int src = _find_index[v];
//The shortest path to the initial point
dest.resize(n, W_MAX);
//Vertex parent subscript
parentPath.resize(n, -1);

dest[src] = W();//Set the starting point to 0
vector<bool> visited(n, false);
//Execute n times
for (int i = 0; i < n; i + + )
{
int minW = W_MAX, minI = src;
//Find the current minimum vertex and it is not used
for (int j = 0; j < n; j + + )
{
if (visited[j] == false & amp; & amp; dest[j] < minW)
{
minI = j;
minW = dest[j];
}
}
//Set to the used value, it cannot be smaller
visited[minI] = true;

//Whether extension can find smaller vertex weights
for (int j = 0; j < n; j + + )
{
//Satisfy unused, right side of two vertices
if (visited[j] == false & amp; & amp; _matrix[minI][j] != W_MAX)
{
//The new path value is smaller
if (dest[minI] + _matrix[minI][j] < dest[j])
{
//Set path value and parent vertex subscript
dest[j] = dest[minI] + _matrix[minI][j];
parentPath[j] = minI;
}
}
}
}
}

void TestGraphDijkstra()
{
const char* ch = "syztx";
vector<char> v;
for (int i = 0; i < strlen(ch); i + + )
{
v.push_back(ch[i]);
}
Matrix::Graph<char, int, true, INT_MAX > g(v);
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('y', 't', 3);
g.AddEdge('y', 'x', 9);
g.AddEdge('y', 'z', 2);
g.AddEdge('z', 's', 7);
g.AddEdge('z', 'x', 6);
g.AddEdge('t', 'y', 2);
g.AddEdge('t', 'x', 1);
g.AddEdge('x', 'z', 4);

vector<int> dest;
vector<int> parentPath;
g.Dijkstra('s', dest, parentPath);
}

 bool BellmanFord(const V & amp; v, vector<W> & amp; dest, vector<int> & amp; parentPath)
{
int n = _vertexs.size();
int src = _find_index[v];//Initial position

dest.resize(n, W_MAX);
parentPath.resize(n, -1);

//Initialize initial position
dest[src] = 0;

//Why is it n-1 times: from any vertex to all other vertices at most n-1 times, further explanation will form a negative weight loop
for (int k = 0; k < n - 1; k + + )
{
bool quit = true;
//Traverse the weight adjacency matrix
for (int i = 0; i < n; i + + )
{
for (int j = 0; j < n; j + + )
{
                        //There is an edge and it is not an initial value
if (_matrix[i][j] != W_MAX & amp; & amp; dest[i] != W_MAX & amp; & amp; dest[i] + _matrix[i][j] < dest[j])
{
//Set smaller path value and parent vertex subscript
dest[j] = dest[i] + _matrix[i][j];
parentPath[j] = i;
quit = false;
}
}
}
if (quit)
break;
}

//Determine whether a negative weight loop is formed
for (int i = 0; i < n; i + + )
{
for (int j = 0; j < n; j + + )
{
if (_matrix[i][j] != W_MAX & amp; & amp; dest[i] != W_MAX & amp; & amp; dest[i] + _matrix[i][j] < dest[j])
return false;
}
}
return true;
}

void TestGraphBellmanFord()
{
const char* ch = "syztx";
vector<char> v;
for (int i = 0; i < strlen(ch); i + + )
{
v.push_back(ch[i]);
}
Matrix::Graph<char, int, true, INT_MAX> g(v);
g.AddEdge('s', 't', 6);
g.AddEdge('s', 'y', 7);
g.AddEdge('y', 'z', 9);
g.AddEdge('y', 'x', -3);
g.AddEdge('z', 's', 2);
g.AddEdge('z', 'x', 7);
g.AddEdge('t', 'x', 5);
g.AddEdge('t', 'y', 8);
g.AddEdge('t', 'z', -4);
g.AddEdge('x', 't', -2);
vector<int> dist;
vector<int> parentPath;
if (g.BellmanFord('s', dist, parentPath))
{
}
else
{
cout << "There is a negative weight loop" << endl;
}
}

 void FloydWarShall(vector<vector<W>> & amp; vvDest, vector<vector<int>> & amp; vvParentPath)
{
int n = _vertexs.size();
vvDest.resize(n);
vvParentPath.resize(n);
//Initialization
for (int i = 0; i < n; i + + )
{
vvDest[i].resize(n, W_MAX);
vvParentPath[i].resize(n, -1);
}
//Add directly connected vertices to the two-dimensional array
for (int i = 0; i < n; i + + )
{
for (int j = 0; j < n; j + + )
{
if (_matrix[i][j] != W_MAX)
{
vvDest[i][j] = _matrix[i][j];
vvParentPath[i][j] = i;
}
else
{
vvParentPath[i][j] = -1;
}
if (i == j)
{
vvParentPath[i][j] = -1;
vvDest[i][j] = 0;
}
}
}
\t\t\t
//Dynamic rule idea: There is a k between i to j, and i to k + k to j < i to j
for (int k = 0; k < n; k + + )
{
for (int i = 0; i < n; i + + )
{
for (int j = 0; j < n; j + + )
{
if (vvDest[i][k] != W_MAX & amp; & amp; vvDest[k][j] != W_MAX & amp; & amp; vvDest[i][k] + vvDest[k][j] < vvDest[i][j])
{
\t\t\t\t\t\t\t
vvDest[i][j] = vvDest[i][k] + vvDest[k][j];
vvParentPath[i][j] = vvParentPath[k][j];
}
}
}
}

}

void TestFloydWarShall()
{
const char* ch = "12345";
vector<char> v;
for (int i = 0; i < strlen(ch); i + + )
{
v.push_back(ch[i]);
}
Matrix::Graph<char, int, true, INT_MAX> g(v);
g.AddEdge('1', '2', 3);
g.AddEdge('1', '3', 8);
g.AddEdge('1', '5', -4);
g.AddEdge('2', '4', 1);
g.AddEdge('2', '5', 7);
g.AddEdge('3', '2', 4);
g.AddEdge('4', '1', 2);
g.AddEdge('4', '3', -5);
g.AddEdge('5', '4', 6);
vector<vector<int>> vvDist;
vector<vector<int>> vvParentPath;
g.FloydWarShall(vvDist, vvParentPath);

}