1

我对图表仍然很陌生，并且正在为一个学校项目构建一个加权有向图。我能够完成所有功能，除了找到从一个节点到另一个节点的最小加权路径的功能。我能够找到一条路径，但不知道如何存储所有路径然后获得最小加权路径。我的图表由一个向量表示。

我创建了一个辅助函数，它为我提供了一条从源到目的地的路径，以及一个找到路径权重的函数。它们都可以工作，但我无法找到找到所有路径的路径而不是找到的第一个路径。

int WeightedDigraph::Myhelp(int to) const{
    for (mytup::const_iterator k = adjList.begin(); k != adjList.end(); ++k) {
        if(get<1>(*k) == to){ //destination
                return get<0>(*k); //source
        }
    }
    return 10000;
}

list<int> WeightedDigraph::FindMinimumWeightedPath(int from, int to) const {
    list<int> minpath;
    minpath.push_front(to);
    int src = Myhelp(to);
    while(src != from){
        minpath.push_front(src);
            src = Myhelp(src);
    }
    return minpath;
}

此代码返回从“from”到“to”的“a”路径列表。相反，我希望它返回重量最小的那个。我必须使用已设置的函数 getPathWeight(const list& path) 来查找每条路径的权重并进行比较，但是我怎样才能将所有路径放在一个地方？

更新最低限度的工作示例，包括：

主文件

    #include "WeightedDigraph.h"
#include <iostream>
#include <string>
#include <list>
using namespace std;

int main(int argc, char* argv[])
{

    if(argc != 4) {
        cerr << "Incorrect number of command line arguments." << endl;
        cerr << "Usage: " << argv[0] << " <filename> <start vertex> <dest vertex>" << endl;
        exit(EXIT_FAILURE);
    }

    WeightedDigraph graph(argv[1]);

    cout << "The graph has " << graph.GetOrder() << " vertices and " << graph.GetSize() << " arcs" << endl;

    int source = atoi(argv[2]);
    int dest = atoi(argv[3]);

    if (graph.DoesPathExist(source, dest)) {
        list<int> path = graph.FindMinimumWeightedPath(source, dest);
        //then the path will be used for other functions
    return 0;
}

WeightedDiagraph.cpp：

#include "WeightedDigraph.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <limits>
#include<list>

using namespace std;


void WeightedDigraph::InsertArc(int from, int to, double weight) {
    tuple<int, int, double> newtup (from, to, weight); 
    adjList.push_back(newtup);
}

double WeightedDigraph::GetPathWeight(const list<int> & path) const {
    //working
}

//other functions that are not needed for my question

加权图.h：

#ifndef WeightedDigraph_H
#define WeightedDigraph_H

#include<list>
#include<string>
#include<vector>
#include<tuple>

using namespace std;

typedef vector<tuple<int,int,double>> mytup;

class WeightedDigraph {
public:
    mytup adjList;
    //all methods

private:
    int numVertices;
    int numArcs;

    int from;
    int to;
    double weight;

}
4

0 回答 0