Найти минимально взвешенный путь в векторе кортежей, представляющих граф - PullRequest
Новая
       53

Найти минимально взвешенный путь в векторе кортежей, представляющих граф

1 голос
/ 17 апреля 2019

Я все еще плохо знаком с графами и строю взвешенный ориентированный граф для школьного проекта.Мне удалось выполнить все функции, кроме той, которая находит минимально взвешенный путь от узла к другому.Я могу найти путь, но не знаю, как мне сохранить все пути, а затем получить минимально взвешенный.Мой график представлен вектором.

Я создал вспомогательную функцию, которая дает мне путь от источника до места назначения, и функцию, которая находит вес пути.Они оба работают, но я не могу получить тот, который находит путь, чтобы найти все пути вместо первого, который он находит. 

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;
}

Этот код возвращает список для "a" path from "из"чтобы" чтобы ".Вместо этого я хочу вернуть тот, у которого наименьший вес.Я должен настроить уже настроенную функцию getPathWeight (список констант и путь), чтобы найти вес каждого пути и сравнить их, но как мне получить все пути в одном месте?

Обновление для минимального рабочего примера с включениями:

Main.cpp 

    #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

WeightedDiagraph.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;

}
...