CODEWITHSUNDEEP
c++listgraphweighted
user2963379
user2963379

Reputation: 165

Implementing a weighted BFS to find shortest path

I'm using an adjacency list and my addEdge function looks like this:

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

Which would be fine except I need to know the weight of the edge. Just can't wrap my head around it at the moment.

Upvotes: 0

Views: 381

Answers (1)

sdzivanovich
sdzivanovich

Reputation: 760

You could define a class to hold both the weight and endpoint of the edge:

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

Naturally, this will require modifications to your Graph; adj would need to store Edges rather than ints. If that isn't feasible, you could map edges to weights like so:

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

such that for a given edge u-v, edgeWeights[u][v] is the weight of edge u-v.

Similarly, you could also map pairs (i.e. edges) to weights:

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

The possibilities are endless.

Upvotes: 1

Related Questions