C语言求解无向图顶点之间的所有最短路径

 std::vector tempPath; std::vector> totalPath;

 //查找无向图的所有最短路径，直接dfs就可以解决了 //记录保存这里用 vector> 插入失败，重新搞一下 OK // 时间复杂度 O（N + E） #include  #include  #include  #include  #include  #define MAX 10 #define INF 999999 int graph[MAX + 1][MAX + 1]; int N, M;          //node, edge int nodeBook[MAX + 1]; int minPath = INF; std::vector pathNodeVec; std::vector> allShortVec; int startNode, endNode; void dfs(int i, int step) { if (i == endNode) {   //遇到终点，进行路径判定 if (step  tempVec = pathNodeVec; allShortVec.clear();            //清空 allShortVec.push_back(tempVec);      //存储 pathNodeVec.pop_back(); } else if (step == minPath) { std::cout << "step == minpath.., size = " << allShortVec.size() << std::endl; pathNodeVec.push_back(i); for (auto &elem : pathNodeVec) std::cout << elem << "\t"; std::cout << std::endl; std::vector tempVec = pathNodeVec; allShortVec.push_back(tempVec);     //存储当前路径 pathNodeVec.pop_back(); } else { ;} return; } nodeBook[i] = 1; pathNodeVec.push_back(i); for (int x = 1; x <= N; x++) {   //尝试所有可能性 if (x == i) continue; if (nodeBook[x] == 1) continue; if (graph[i][x] == INF) continue; dfs(x, step + 1); } nodeBook[i] = 0; pathNodeVec.pop_back(); return ; } int main(void) { std::cin >> N >> M; for (int x = 1; x <= N; x++) nodeBook[x] = 0;    //表示还没有访问 for (int x = 1; x <= N; ++x) for (int y = 1; y <= N; ++y) { if (x == y) graph[x][y] = 0; else graph[x][y] = INF; } for (int i = 1; i <= M; ++i) { int tempX, tempY, tempWeight; std::cin >> tempX >> tempY >> tempWeight; graph[tempX][tempY] = tempWeight; } std::cout << "please input start node & end node :" << std::endl; std::cin >> startNode >> endNode; pathNodeVec.clear(); allShortVec.clear(); dfs(startNode, 0); std::cout << "all shortest path: \t"; std::cout << "size = " << allShortVec.size() << std::endl; for (std::vector>::const_iterator it = allShortVec.begin(); it != allShortVec.end(); it++) { for (std::vector::const_iterator it2 = (*it).begin(); it2 != (*it).end(); it2++) std::cout << (*it2) << "\t"; std::cout << std::endl; } getchar(); return 0; }