What is a good way to store the computation of the distance into a matrix?

[WhatHaveIChoosen22]

Hi,
So I'm working on a search algorithm, however, we were asked to compute the distance between the nodes(points(x,y)), and once the distance is computed, then store it into a matrix, which then we perform a look up and let the search algorithm know which distance is closer to the goal node, and hence it will follow that route, and adding the distances.

Here's my question: I been looking all over to find an specific examples, but did not find any. The problem is that my points are read from a input file(.txt), so while I am able to get it to read the input files and get the x's and y's, I am still lost on how can I compute their distances of each two points and then storing it to a matrix.

This what I have so far:

...
int main() {

const int maxSize = 4;
int x, y, xPoint[maxSize], yPoint[maxSize];
double distance;
Graph g(4); //Creates n vertices
ifstream file("test.txt");
while(!file.eof()) {
    for(int i = 0; i < maxSize; i++)
    {
        file >> xPoint[i];
        file >> yPoint[i];
        cout << xPoint[i] << " " << yPoint[i] << endl;

        distance = sqrt(pow(xPoint[i+1]-xPoint[i], 2) + pow(yPoint[i+1]-yPoint[i], 2));
    }


    //g.addEdge(x, y); 
    //g.BestFirstSearch(0); //Start from first as root.
}   

cout << endl;
cout << distance << "" << endl; //To test if distances compute working

return 0;

}

Any help would be appreciated.

[48T7M4Gy]

The distance calculation looks about right. It’s probably better to just multiply the two numbers eg x*x rather than use pow, but that’s only a small point.

Since the distance is between two points say i and j, d will be in position [i][j] of the matrix. And the matrix will be symmetrical, believe it or not

[WhatHaveIChoosen22]

Like so?:

distance = sqrt(pow(xPoint[i+1]-xPoint[i], 2) + pow(yPoint[i+1]-yPoint[i], 2));
matrix[i][j] = distance;

[48T7M4Gy]

That’s the way, however you have to translate the relationship between i,j i+1, they’re a bit jumbled.

You are better off reading in the points into an array or vector, then when that’s complete and once you know how the points are connected, work out the distances and store them in the matrix

matrix[i][j] = sqrt(pow(x[i] - x[j],2) etc ) You have to specify what i and j are from which point i is connected to point j in the list of points. That info should be given to you unless therecis some other arrangement or data you are supplied with.

[WhatHaveIChoosen22]

hmmm, I'll give it a try and see what happens, and will let you know if I get stuck. Thanks!

[48T7M4Gy]

One other thought crops up. If you are required to get the distances between all ponts, the sytem is still the same but the problem of selecting i and j is very simple, it’s just nested loops through all the points. if i == j then the distance is zero.

[keskiverto]

If you just need shortest distance, then the sqrt is unnecessary before the search. We do know that A and B are both positive (there is no negative distance). Therefore:

A*A < B*B
<=>
A < B

You have a Graph. Custom type. You could, for fun, write struct Point with necessary operators. Then your main() could look simpler:

std::ifstream file("test.txt");
std::vector<Point> points;
Point input;
while ( file >> input ) {
  points.push_back( input );
}
for ( int row = ... ) {
  for ( int col = ... ) {
    matrix[row][col] = distance( points[row], points[col] );
  }
}