Реализация взвешенной BFS, чтобы найти кратчайший путь

Question

Реализация взвешенной BFS, чтобы найти кратчайший путь

Я использую список смежности, и моя функция addEdge выглядит так:

void Graph::addEdge(int start, int end, int weight)
{
adj[start].push_back(end);
}

Что было бы хорошо, за исключением того, что мне нужно знать вес края. Просто не могу обернуть голову вокруг этого в данный момент.

0

c++graph list weighted

Решение

Другие решения

Источник

Accepted Answer

Вы можете определить класс для хранения веса и конечной точки ребра:

class Edge
{
public:
int endpoint;
int weight;
};

Естественно, это потребует модификации вашего Графика; adj нужно хранить Edgeскорее, чем ints. Если это невозможно, вы можете сопоставить ребра весам следующим образом:

std::vector<std::vector<int> > edgeWeights;

такой, что для данного ребра U-V, edgeWeights[u][v] это вес ребра U-V.

Точно так же вы могли бы также отобразить пары (то есть ребра) на веса:

std::map<std::pair<int, int>, int> edgeWeights;

Возможности безграничны.

1