寻找有向图的最短路径 C++

Question

在过去的一周中，我通过解析输入文件来实现了有向图。该图保证没有循环。我成功地创建了图形，使用方法返回了顶点和边的数量，并对图形执行了拓扑排序。该图由不同的主要课程及其先决条件组成。这是我的图形设置：

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天，但无济于事。我是否设置了错误的有向图来实现这些步骤？任何指导都将不胜感激。

- kemotoe

---

听起来像是一些旅行商问题。 - dwcanillas

如果没有循环，你如何回到原始顶点？回溯吗？ - Sean Kuhlman

你的意思是有向图 - 有向图和另一种完全不同。 - Useless

@dwcanillas 这是为大学设置的课程地图。权重是需要注册课程的分数。 - kemotoe

@kemotoe 这不相关，它们仍然基本上是旅行推销员问题 - 请阅读该页面。 - dwcanillas

Answer 1

没有循环的事实使问题变得简单许多。找到最短路径和最小“大回路”都是O(n)的。

实现Dijkstra算法并运行它，没有“目标”节点；只需一直走下去，直到所有节点都被访问过。一旦每个节点都被标记（带有其到根的距离），您就可以从任何节点开始，并通过始终向距此节点距离较小的唯一邻居迈进来跟随最短（且仅有的）路径返回到根。如果您愿意，在进行此操作时可以轻松构建这些路径，并使用完整路径将每个节点标记回根，但是如果不小心复制这些路径可能会将成本推高到O(n²)。

一旦所有节点都被标记，您就可以构建一个最小的大回路。从根开始；当您访问一个节点时，请迭代其未访问的邻居（即除了您刚刚来自的那个节点外的所有邻居），然后返回您来自的节点。（如果您喜欢，我可以用更多数学严谨性说明，或者给出一个例子。）

- Beta

---

一个例子会很好。我已经尝试实现你建议的方法，但没有成功。 - kemotoe