floyd源码实现C++

//#include<iostream> //#include<vector> //#include<stack> //using namespace std; // //#define INF 100001 //#define maxv 100 //vector<int> st; // //stack<int> stk; //int eTop = 0; //int src[maxv][maxv]; //用于存储结点到结点之间的最短路径距离 //int path[maxv][maxv]; //用于存储所经过的节点 // ////边的结构体 //struct Edge //{ // int u, v, len; //起点，终点，权 // Edge* next; //下一条边 //}epool[maxv]; // ////点的结构体 //struct Node //{ // Edge* first; //第一条边 //}; // ////图的结构体 //struct Graph //{ // int e, n; //边数与顶点数 // Node adj[maxv]; //}; // ////测试的数据 //class Data //{ //public: // Data(int u, int v, int len) // { // this->m_u = u; // this->m_v = v; // this->m_len = len; // } // int m_u; // int m_v; // int m_len; //}; // //void insertData(vector<Data>& vd) //{ // Data d1(1, 2, 4); // Data d2(1, 3, 6); // Data d3(1, 4, 6); // Data d4(2, 3, 1); // Data d5(2, 5, 7); // Data d6(3, 5, 6); // Data d7(3, 6, 4); // Data d8(4, 3, 2); // Data d9(4, 6, 5); // Data d10(5, 7, 6); // Data d11(6, 5, 1); // Data d12(6, 7, 8); // vd.push_back(d1); // vd.push_back(d2); // vd.push_back(d3); // vd.push_back(d4); // vd.push_back(d5); // vd.push_back(d6); // vd.push_back(d7); // vd.push_back(d8); // vd.push_back(d9); // vd.push_back(d10); // vd.push_back(d11); // vd.push_back(d12); //} // //void initArray(Graph& g, int src[maxv][maxv], int path[maxv][maxv]) //{ // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // if (i == j) // { // src[i][j] = 0; // } // else // { // src[i][j] = INF; // } // } // } // for (int i = 1; i <= g.n; i++) // { // while (g.adj[i].first) // { // src[i][g.adj[i].first->v] = g.adj[i].first->len; // g.adj[i].first = g.adj[i].first->next; // } // } // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // if (i != j && src[i][j] < INF) //i到j有边时 // { // path[i][j] = i; // } // else // { // path[i][j] = -1; //i到j有边时 // } // } // } //} // //void printArray(Graph& g, int array[maxv][maxv]) //{ // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // cout << "\t" << array[i][j] << " "; // } // cout << endl; // } //} // //bool dfs(Graph& g, int u) //{ // st[u] = 1; //正在dfs // while (g.adj[u].first) // { // int v = g.adj[u].first->v; // if (st[v] == 1) // { // return true; // } // if (st[v] == 0 && dfs(g, v)) // { // return true; // } // g.adj[u].first = g.adj[u].first->next; // } // st[u] = -1; //结束 // stk.push(u); // return false; //} // //void addEdge(Graph& g, int u, int v, int len) //{ // epool[eTop].u = u; // epool[eTop].v = v; // epool[eTop].len = len; // epool[eTop].next = g.adj[u].first; // g.adj[u].first = &epool[eTop]; // eTop++; //} // //void creatGraph(Graph& g) //{ // vector<Data> vd; // insertData(vd); // g.n = 7; // st.assign(g.n + 1, 0); //将st数组内的值初始化为0 // for (int i = 1; i <= g.n; i++) // { // g.adj[i].first = NULL; //将每个顶点的初始值置为空 // } // g.e = vd.size(); // for (auto it = vd.begin(); it != vd.end(); it++) // { // addEdge(g, (*it).m_u, (*it).m_v, (*it).m_len); // } // Graph g1 = g; // for (int i = 1; i <= g.n; i++) // { // if (!st[i] && dfs(g1, i)) // { // cout << "图中有环！" << endl; // } // } //} //void displayPath(Graph& g, int src[maxv][maxv], int path[maxv][maxv]) //{ // stack<int> aPath; // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // if (i != j && src[i][j] < INF) //存在路径 // { // cout << "从" << i << "到" << j << "的路径为：" << " "; // aPath.push(j); // int k = path[i][j]; // while (k != -1 && k != i) // { // aPath.push(k); // k = path[i][k]; // } // if (k == i) // { // aPath.push(i); // } // //打印路径 // while (!aPath.empty()) // { // if (aPath.size() == 1) // { // cout << aPath.top() <<" "; // aPath.pop(); // } // else // { // cout << aPath.top() << "->"; // aPath.pop(); // } // } // cout << "最短路径长度为：" << src[i][j] << endl; // } // } // } //} // //void flody(Graph& g, int src[maxv][maxv], int path[maxv][maxv]) //{ // for (int k = 1; k <= g.n; k++) // { // for (int i = 1; i <= g.n; i++) // { // for (int j = 1; j <= g.n; j++) // { // if (src[i][j] > src[i][k] + src[k][j]) // { // src[i][j] = src[i][k] + src[k][j]; // path[i][j] = path[k][j]; // } // } // } // } //} // //int main() //{ // Graph g; // creatGraph(g); // while (!stk.empty()) // { // cout << stk.top() << " "; // stk.pop(); // } // cout << endl; // initArray(g, src, path); // cout << "---------Flody前----------" << endl; // printArray(g, src); // cout << "--------------------------" << endl; // printArray(g, path); // flody(g, src, path); // cout << "---------Flody后----------" << endl; // printArray(g, src); // cout << "--------------------------" << endl; // printArray(g, path); // cout << "--------------------------" << endl; // displayPath(g, src, path); // system("pause"); // return 0; //}