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

5星 · 超过95%的资源 90 浏览量更新于2023-03-16 评论收藏 68KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

主要为大家详细介绍了C语言求解无向图顶点之间的所有最短路径，具有一定的参考价值，感兴趣的小伙伴们可

以参考一下

本文实例为大家分享了C语言求解无向图顶点之间的所有最短路径的具体代码，供大家参考，具体内容如下

思路一：思路一：

DFS，遇到终点之后进行记录

辅助存储：

std::vector<int> tempPath;

std::vector<std::vector<int>> totalPath;

实现：

//查找无向图的所有最短路径，直接dfs就可以解决了

//记录保存这里用 vector<vector<int>> 插入失败，重新搞一下 OK

// 时间复杂度 O（N + E）

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <set>

#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<int> pathNodeVec;

std::vector<std::vector<int>> allShortVec;

int startNode, endNode;

void dfs(int i, int step)

{

if (i == endNode) { //遇到终点，进行路径判定

if (step < minPath) {

std::cout << "step < minpath.., size = " << allShortVec.size() << std::endl;

minPath = step;

pathNodeVec.push_back(i);

for (auto &elem : pathNodeVec)

std::cout << elem << " ";

std::cout << std::endl;

std::vector<int> 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 << " ";

std::cout << std::endl;

std::vector<int> 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();

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

光与火花

2023-07-28

：文件中的代码清晰明了，用简洁的语言解释了求解无向图顶点最短路径的步骤。

weixin_38706055

粉丝: 5
资源: 909

会员权益专享

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

评论5

会员权益专享

最新资源

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

评论5

带权无向网求最短路径

深度优先求无向图中顶点a到顶点i的最短路径

图中任意两点间所有路径高效算法

动态Dijkstra算法实现动态最短路径

c语言无向图邻接表最短路径

Dijkstra算法求解无向图中的单源最短路径给出C语言代码

用c语言写一个求解无向图遍历完所有点走过的最短路径问题，并打印出最短路径

用c语言写一个求解无向图遍历完所有点走过的最短路径问题

c语言实现求带权无向图中单源最短路径的迪克斯特拉算法的代码

用c语言写一个求解带权无向图遍历完所有点走过的最短路径问题，并打印出最短路径

无向图最短路径c语言代码

最短路径动态规划C语言

使用迪杰斯特拉算法求出任意两点的最短路径c语言代码

使用迪杰斯特拉算法求出无向加权图中任意两点的最短路径并输出其路径c语言代码

在程序中直接导入加权无向图使用迪杰斯特拉算法求任意两点的最短路径及其最短值c语言代码

c语言动态规划最短路径问题

用C语言求图的中心顶点问题

会员权益专享

最新资源