gsharma34065
BAN USER- -1of 1 vote
AnswersGiven an un-directed weighted graph G(V,E), find the minimum weight between two given nodes X & Y
- gsharma34065 in India
(i.e. sum of weights of edges between X & Y).
You can add an extra egde with weight W between any two nodes in the graph exactly one time (if required).| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
Basic solution would be to recur for both possibilities. A function can be written like below.
Assuming x & y is current location and dx & dy are destination.
bool isReachable(int x, int y, int dx, int dy)
{
// Destination reached
if((x == dx) && (y == dy))
return true;
// Limit exceeds
if((x > dx) || (y > dy))
return false;
// Only two ways left to traverse
return isReachable(x + y, y, dx, dy) || isReachable(x, x + y, dx, dy);
}
Well it depends on the representation of your graph, like in which way are you trying to represent it - Matrix form or list form. Copying via list form will always take less space.
There may be other ways for copying it, for example. you can write list representation in a text file like this :
1 : 2,3,4
2 : 1,5
4 : 3,5
i.e. 1st node has an edge from 1 to 2,3 and 4. 2nd has edge from 2 to 1 and 5 etc.
You can read above text file while creating graph.
First can be solved by basic recursion.
- gsharma34065 October 15, 2016