I am trying to find the path between two vertices and their distance. My implementation is the following:
#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;
vector <string> v1 = {"Prague", "Helsinki", "Beijing", "Tokyo", "Jakarta","London", "New York"};
vector <int> w = {};
// A directed graph using
// adjacency list representation
class Graph {
int V; // No. of vertices in graph
list<int>* adj; // Pointer to an array containing adjacency lists
// A recursive function used by printAllPaths()
void printAllPathsUtil(int, int, bool[], int[], int&);
public:
Graph(int V); // Constructor
void addVertex(string name);
void addEdge(int u, int v, int weight);
void printAllPaths(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v, int weight)
{
adj[u].push_back(v); // Add v to u’s list.
w.push_back(weight);
}
// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
// Mark all the vertices as not visited
bool* visited = new bool[V];
// Create an array to store paths
int* path = new int[V];
int path_index = 0; // Initialize path[] as empty
// Initialize all vertices as not visited
for (int i = 0; i < V; i )
visited[i] = false;
// Call the recursive helper function to print all paths
printAllPathsUtil(s, d, visited, path, path_index);
}
// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int& path_index)
{
// Mark the current node and store it in path[]
visited[u] = true;
path[path_index] = u;
path_index ;
int sum = 0;
// If current vertex is same as destination, then print
// current path[]
if (u == d) {
for (int i = 0; i < path_index; i ){
sum = w[i];
cout << v1[path[i]] << " ";
}
cout << endl;
cout << "Total distance is: " << sum;
cout << endl;
}
else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
// Remove current vertex from path[] and mark it as unvisited
path_index--;
visited[u] = false;
}
// Driver program
int main()
{
// Create a graph given in the above diagram
Graph g(7);
g.addEdge(0, 1, 1845);
g.addEdge(0, 5, 1264);
g.addEdge(1, 3, 7815);
g.addEdge(2, 5, 8132);
g.addEdge(2, 6, 11550);
g.addEdge(2, 3, 1303);
g.addEdge(3, 4, 5782);
g.addEdge(3, 6, 10838);
g.addEdge(4, 2, 4616);
g.addEdge(5, 3, 9566);
g.addEdge(6, 5, 5567);
int s = 0, d = 2;
cout << "Following are all different paths from " << v1[s] << " to " << v1[d] << endl;
g.printAllPaths(s, d);
return 0;
}
Obviously this part is wrong:
vector <int> w = {};
w.push_back(weight);
int sum = 0;
// If current vertex is same as destination, then print
// current path[]
if (u == d) {
for (int i = 0; i < path_index; i ){
sum = w[i];
cout << v1[path[i]] << " ";
}
cout << endl;
cout << "Total distance is: " << sum;
cout << endl;
Output is:
Prague Helsinki Tokyo Jakarta Beijing
Total distance is: 30606
Prague London Tokyo Jakarta Beijing
Total distance is: 30606
This is wrong (but the path is correct) because of my implementation, it prints out the summation of the overall first 5 weights. But I just did not understand how can I get the weights
How can I get the corresponding weights and add them up?
What I expect:
Prague Helsinki Tokyo Jakarta Beijing
Total distance is: 20058
Prague London Tokyo Jakarta Beijing
Total distance is: (There will be some number I have not calculated yet)
CodePudding user response：
There are two main problems here. When you create the edges you do not coupled their cost to them in any way. Also when you traverse them in your algorithm you do not save the cost of traversing the edge, you only save the cities.
Here is a simple solution if you want to keep almost an identical structure. You can accompany the adjecency lists with a list of the costs for each such edge. Son instead of having the w array you can have one such for each noce (city). Then the path array can also be accompanied by another int array with the costs of each step.
Starting with defining and creating the edges it would be:
class Graph {
int V; // No. of vertices in graph
list<int>* adj; // Pointer to an array containing adjacency lists
list<int>* adj_weights; // Pointer to an array containing adjacency lists
...
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
adj_weights = new list<int>[V];
}
void Graph::addEdge(int u, int v, int weight)
{
adj[u].push_back(v); // Add v to u’s list.
adj_weights[u].push_back(weight); // Add the weight of the path as well.
}
Now we have stored the weights and the edges together in a better way, but we still need to use this in the algorithm. Here is an example change of the main functions:
// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
// Mark all the vertices as not visited
bool* visited = new bool[V];
// Create an array to store paths
int* path = new int[V];
int* path_costs = new int[V];
int path_index = 0; // Initialize path[] and path_costs[] as empty
// Initialize all vertices as not visited
for (int i = 0; i < V; i )
visited[i] = false;
// Call the recursive helper function to print all paths
// Note that we let cost = 0 since we don't have to move to the starting city
printAllPathsUtil(s, d, visited, path_costs, path, path_index, 0);
}
// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[], int path_costs[],
int path[], int& path_index, int cost)
{
// Mark the current node and store it in path[]
visited[u] = true;
path[path_index] = u;
path_costs[path_index] = cost; // Save cost of this step
path_index ;
int sum = 0;
// If current vertex is same as destination, then print
// current path[]
if (u == d) {
for (int i = 0; i < path_index; i ){
sum = path_costs[i]; // Now add all the costs
cout << v1[path[i]] << " ";
}
cout << endl;
cout << "Total distance is: " << sum;
cout << endl;
}
else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
// Now we loop over both adj and adj_weights
list<int>::iterator i, j;
for (i = adj[u].begin(), j = adj_weights[u].begin();
i != adj[u].end(); i, j)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path_costs, path,
path_index, *j);
}
// Remove current vertex from path[] and mark it as unvisited
path_index--;
visited[u] = false;
}
You can see a full version of the augmented code here https://ideone.com/xGju0y and it gives the following output:
Following are all different paths from Prague to Beijing
Prague Helsinki Tokyo Jakarta Beijing
Total distance is: 20058
Prague London Tokyo Jakarta Beijing
Total distance is: 21228
I hope this helps! I tried to focus on using the same concepts you introduced to not solve things with some new classes or imports. But there are much nicer ways to solve this. One example is to merge the path and path_weights arrays into one array of pairs of ints, and to merge adj and adj_weights into an array of lists of pairs of ints instead of an array of lists of ints.