在上周,我通过解析输入文件实现了有向图。该图保证没有循环。我已经成功创建了图,使用方法返回了顶点和边的数量,并对图进行了拓扑排序。该图由不同的主要类(class)及其先决条件组成。这是我的图表设置:
class vertex{
public:
typedef std::pair<int, vertex*> ve;
std::vector<ve> adjacency;
std::string course;
vertex(std::string c){
course = c;
}
};
class Digraph{
public:
typedef std::map<std::string, vertex *> vmap;
vmap work;
typedef std::unordered_set<vertex*> marksSet;
marksSet marks;
typedef std::deque<vertex*> stack;
stack topo;
void dfs(vertex* vcur);
void addVertex(std::string&);
void addEdge(std::string& from, std::string& to, int cost);
int getNumVertices();
int getNumEdges();
void getTopoSort();
};
实现
//function to add vertex's to the graph
void Digraph::addVertex(std::string& course){
vmap::iterator iter = work.begin();
iter = work.find(course);
if(iter == work.end()){
vertex *v;
v = new vertex(course);
work[course] = v;
return;
}
}
//method to add edges to the graph
void Digraph::addEdge(std::string& from, std::string& to, int cost){
vertex *f = (work.find(from)->second);
vertex *t = (work.find(to)->second);
std::pair<int, vertex *> edge = std::make_pair(cost, t);
f->adjacency.push_back(edge);
}
//method to return the number of vertices in the graph
int Digraph::getNumVertices(){
return work.size();
}
//method to return the number of edges in the graph
int Digraph::getNumEdges(){
int count = 0;
for (const auto & v : work) {
count += v.second->adjacency.size();
}
return count;
}
//recursive function used by the topological sort method
void Digraph::dfs(vertex* vcur) {
marks.insert(vcur);
for (const auto & adj : vcur->adjacency) {
vertex* suc = adj.second;
if (marks.find(suc) == marks.end()) {
this->dfs(suc);
}
}
topo.push_front(vcur);
}
//method to calculate and print out a topological sort of the graph
void Digraph::getTopoSort(){
marks.clear();
topo.clear();
for (const auto & v : work) {
if (marks.find(v.second) == marks.end()) {
this->dfs(v.second);
}
}
// Display it
for (const auto v : topo) {
std::cout << v->course << "\n";
}
}
在我实现的最后一部分,我一直在尝试做两件事。找到从第一个顶点到所有其他顶点的最短路径,并找到访问每个顶点并返回到第一个顶点的最短路径。我完全迷失了这个实现。我从阅读中假设我需要使用 Dijkstra 算法来实现它。我过去 3 天一直在尝试,但无济于事。我是否以错误的方式设置了我的有向图来实现这些步骤?任何指导表示赞赏。
最佳答案
没有环的事实使问题简单得多。寻找最短路径和最小的“大旅行”是 O(n)。
实现 Dijkstra 并运行它,没有“目标”节点;继续前进,直到所有节点都被访问过。一旦标记了每个节点(及其到根的距离),您就可以从任何节点开始,并通过始终步进到距离小于该节点的唯一邻居,沿着最短(且唯一)的路径返回根。如果你愿意,你可以很容易地构建这些路径,并用返回根的完整路径标记每个节点,但是复制这些路径可以将成本推到 O(n2) 如果你不小心。
一旦标记了所有节点,您就可以构建一个最小的大巡回赛。从根开始;当您访问一个节点时,遍历其未访问的邻居(即除了您刚刚来自的节点之外的所有节点),访问每个节点,然后返回您来自的节点。 (如果你愿意,我可以用更严格的数学来表达这个,或者举个例子。)
关于c++ - 寻找有向图的最短路径 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30104036/