feel defeated

[zaphraud]

I decided to give it a whack too.

Here's what I've got so far: reading a file of coordinates into the variables I described before in a manner than ensures I have a slight chance of not ruining everything with a missing term in the data file:

No actual algo yet. That's tonight I guess. Gotta meet someone for dinner.

question was the wikipedia summary correct? Because the shortest path thru a set of connected points from one to another is a totally different question than the shortest path thru ALL of the points in a set of connected points, etc etc..

#include <iostream>
#include <fstream>
#include <math.h>

using std::cout;
using std::ifstream;

#define NUMPOINTS 100 //a maximum
#define DIMENTIONS 3 //this isn't really flexible since the file format is hard coded. oh well.
#define MAXCONNECTIONS 12
#define DATAFILE "connections.txt"
//Format: 
//pointID, point x, point y, point z, number of connections, (connected id 1, connected id 2, ...), -1
//the -1 is a terminator that lets me find my typos. I hope. Since I'm not coding any other sanity checking.


float getdistance(int p1,int p2,float *points[NUMPOINTS][DIMENTIONS]);

int main () {
	float points[NUMPOINTS][DIMENTIONS];//3 dimensions worth of coordinates
	float totaldistance[NUMPOINTS]; //total distance from start
	bool visited[NUMPOINTS]; // once set, point does not need calculating again
	int connectedpoints[NUMPOINTS][MAXCONNECTIONS]; //list of connected points, possibly complete.
	int arrivedfrom[NUMPOINTS]; //set when a point's total distance is altered. indicates what node was being visited when 
	int p1=0, p2=0, pmax=0, c=0, nc=0, z=0, error=0;
	float x=0, y=0;

//initial flush the connections array
	for (p1=0; p1<NUMPOINTS; p1++) {
		for (c=0; c<MAXCONNECTIONS; c++) {
			connectedpoints[p1][c]=0;
			}
		}
	p1=0; c=0; //reinitialize after flush

//read file of points and connections
	ifstream file(DATAFILE);
	while(!file.eof() && (error==0)) {
		file >> p1;
		file >> points[p1][0] >> points[p1][1] >> points[p1][2];
		file >> nc;
		for (c=0; c<nc; c++) {
			file >> connectedpoints[p1][c];
			}
		file >> z;
		if (z != -1) {
			cout <<"\n\n HUGE ERROR! p1=" << p1 << " nc=" << nc <<" !!!\n\n";
			error=1;
			}
		}
		file.close();
	return 0;
	}

float getdistance(int p1, int p2, float *points[NUMPOINTS][DIMENTIONS]) {
	float squared=0;
	int d=0;
	for (d=0; d<3; d++) {
		squared+=(points[p1][d]-points[p2][d])*(points[p1][d]-points[p2][d]);
		}
	return sqrt(squared);
	}

Sample connections.txt file that works the input system:

1 3 3 3 2 2 3 -1
2 1 2 3 2 1 3 -1
3 4 5 6 2 1 2 -1

I'm going to assume the last point in the list is the destination and the first point in the list is the origin... I also probably should do a better job of initializing the arrays I haven't coded with yet. Also, the syntax for the subroutine is FUBAR. Oh well.

[zaphraud]

It works. It ain't pretty, but it works.

#include <iostream>
#include <fstream>
#include <math.h>

using std::cout;
using std::ifstream;

#define NUMPOINTS 100 //a maximum
#define DIMENTIONS 3 //this isn't really flexible since the file format is hard coded. oh well.
#define MAXCONNECTIONS 12
#define DATAFILE "connections.txt"
//Format: 
//pointID, point x, point y, point z, number of connections, (connected id 1, connected id 2, ...), -1
//the -1 is a terminator that lets me find my typos. I hope. Since I'm not coding any other sanity checking.
//the first point is the origin
//the last point is the destination

//-----The main data set is globally available-------
float points[NUMPOINTS][DIMENTIONS];//3 dimensions worth of coordinates
float totaldistance[NUMPOINTS]; //total distance from start
bool visited[NUMPOINTS]; // if set, point does not need calculating again
int connectedpoints[NUMPOINTS][MAXCONNECTIONS]; //list of connected points, possibly complete.
int arrivedfrom[NUMPOINTS]; //set when a point's total distance is altered. indicates what node was being visited when 
//----------------------------------------------------

float getdistance(int p1, int p2);
int closestpoint();
void calcneighbors(int p1); //update distances to all unvisited neighbors

int main () {
	int p1=0, p2=0, pmax=0, c=0, nc=0, z=0, error=0;
	int firstpoint=0, lastpoint=0, steps=0;
	float x=0, y=0, d=0;

//clean the arrays
	for (p1=0; p1<NUMPOINTS; p1++) {
		visited[p1]=0;
		arrivedfrom[p1]=0;
		totaldistance[p1]=0;
		for (c=0; c<DIMENTIONS; c++) {
			points[p1][c]=0;
			}		
		for (c=0; c<MAXCONNECTIONS; c++) {
			connectedpoints[p1][c]=0;
			}
		}
	p1=0; c=0; //reinitialize after flush

//read file of points and connections
	ifstream file(DATAFILE);
	while(!file.eof() && (error==0)) {
		file >> p1; 
		if (firstpoint==0) {
			firstpoint=p1; //remember the first point read
			}
		lastpoint=p1; //remember the last point read
		file >> points[p1][0] >> points[p1][1] >> points[p1][2];
		file >> nc;
		for (c=0; c<nc; c++) {
			file >> connectedpoints[p1][c];
			}
		file >> z;
		if (z != -1) {
			cout <<"\n\n HUGE ERROR! p1=" << p1 << " nc=" << nc <<" !!!\n\n";
			error=1;
			}
		}
	file.close();
//DEBUG:
	cout << "First point ID " << firstpoint << "\n" ;
	cout << "Last point ID " << lastpoint << "\n" ;
	cout << "Distance as bird flies: " << getdistance(firstpoint,lastpoint) << "\n";
	cout << "Closest unvisited point: " << closestpoint() << "\n";
//END DEBUG

//BEGIN JOURNEY
	p1=firstpoint;
	calcneighbors(p1);

	while (p1!=lastpoint) {
		visited[p1]=1; //mark current point
		p2=closestpoint();
		cout << "Visited " << p1 << ". Closest unvisited point: " << p2 << " trip distance of " << totaldistance[p2] << "\n"; //DEBUG
		p1=p2; //go to that point
		calcneighbors(p1);
		steps++;
		}
	cout << "Total distance of " << totaldistance[lastpoint] << " with " << steps << " steps.\n";

//SHOW ME THE WAY HOME (the solution)
	p1=lastpoint;
	cout << "Path back: ";
	while (p1 != firstpoint) {
		cout << p1 << " - ";
		p1=arrivedfrom[p1];
		}
	cout << p1 << ".\n";
	}
//
//return distance between two points
//
float getdistance(int p1, int p2) { 
	float squared=0;
	int d=0;
	for (d=0; d<DIMENTIONS; d++) {
		squared+=(points[p1][d]-points[p2][d])*(points[p1][d]-points[p2][d]);
		}
	return sqrt(squared);
	}

//
//return closest unvisited point
//
int closestpoint() {
	int p1=0, point=0;
	float d=0;
	for (p1=0; p1 < NUMPOINTS ; p1++) {
		if (visited[p1]==0 && totaldistance[p1]!=0) { //ignore uncalculated
			if (totaldistance[p1] < d || d==0) { //first found or smaller distance
				d=totaldistance[p1];
				point=p1;
				}
			}
		}
	return point;
	}

//
// Update distances to connected and unvisited points
//
void calcneighbors (int p1) {
	int p2=0, c=0;
	float d=0;
	while (connectedpoints[p1][c]!=0) {
		p2=connectedpoints[p1][c];
		if (visited[p2]==0) {
			d=getdistance (p1,p2);
			cout << p1 << " " << p2 << " " << d << " calculated\n";  //DEBUG
			if (d < totaldistance[p2] || totaldistance[p2]==0) { //if less than or if first time
				totaldistance[p2] = d; //update distance
				arrivedfrom[p2] = p1; //leave a hans-n-gretel breadcrumb
				cout << p1 << " " << p2 << " " << d << " updated\n";  //DEBUG
				}
			}
		c++;
		}
	}

file connections.txt:

1 3 3 3 2 2 3 -1
2 1 2 3 3 1 3 4 -1
3 4 5 6 4 5 1 2 4 -1
4 4 5 2 3 5 2 3 -1
5 6 6 3 2 4 3 -1

the results:

First point ID 1
Last point ID 5
Distance as bird flies: 4.24264
Closest unvisited point: 0
1 2 2.23607 calculated
1 2 2.23607 updated
1 3 3.74166 calculated
1 3 3.74166 updated
Visited 1. Closest unvisited point: 2 trip distance of 2.23607
2 3 5.19615 calculated
2 4 4.3589 calculated
2 4 4.3589 updated
Visited 2. Closest unvisited point: 3 trip distance of 3.74166
3 5 3.74166 calculated
3 5 3.74166 updated
3 4 4 calculated
3 4 4 updated
Visited 3. Closest unvisited point: 5 trip distance of 3.74166
5 4 2.44949 calculated
5 4 2.44949 updated
Total distance of 3.74166 with 3 steps.
Path back: 5 - 3 - 1.

[icy1]

I think it'd help if you had a more precise specification of the problem that involves Dijkstra to make a solution. (What does input look like, what should output look like, etc.)

Sometimes I find a problem can be overwhelming if it's discussed too abstractly, so it should be narrowed down and made concrete, like a thesis in writing.

[adam2016]

wow nice Zaph :o

I am still trying solutions

[zaphraud]

Yeah, I'm still not totally sure the program is running correctly. The output is certainly a hot mess because I didn't comment out the debug lines. I just posted up the code.

The above needs:
1. A test case that involves more than five points that really only present a couple of paths from start to end. Can't even truly say I am sure I did it right. Just that it worked thru and seemed to get an answer that was reasonable...
2. The ability to handle conditions where there is no path from start to end. I haven't tested what sort of failure the current program produces instead, but even if the core fails gracefully, the reporting mechanism at the end is gonna get stuck at a point 0, constantly going back to point 0...
3. All sorts of sanity checking at other points. The *only* thing I put in was a check for -1 at the expected end of each line because I intended to make a quick and dirty file by hand and didn't want to have to deal with missing terms and reading data from the next line as a source of bugs.

A properly written program shouldn't be able to be hung or crashed by its input file. This program is full of such vulnerabilities. Just toss a large number in the list of connections, and bang, segmentation fault:

1 3 3 3 2 2 3 -1
2 1 2 3 3 1 3 4 -1
3 4 5 6 4 5 1 2 4000 -1
4 4 5 2 3 5 2 3 -1
5 6 6 3 2 4 3 -1

$ ./dijkstra.exe
First point ID 1
Last point ID 5
Distance as bird flies: 4.24264
Closest unvisited point: 0
1 2 2.23607 calculated
1 2 2.23607 updated
1 3 3.74166 calculated
1 3 3.74166 updated
Visited 1. Closest unvisited point: 2 trip distance of 2.23607
2 3 5.19615 calculated
2 4 4.3589 calculated
2 4 4.3589 updated
Visited 2. Closest unvisited point: 3 trip distance of 3.74166
3 5 3.74166 calculated
3 5 3.74166 updated
3 4000 inf calculated
Segmentation fault (core dumped)

That's a problem...

[fotob]

For what it's worth, I feel like that a lot too. And I just recently started programming in C++. Previously I was a front-end developer.

When I feel down I usually try to justify why my intellect isn't suitable to be able to work with something as demanding as programming. One thing I found myself doing quite a lot of times is tests. IQ tests, memory tests and whatever you can find laying around on both the web and outside. I usually score in the top 1% percentile.

But, I still struggle. So maybe I'm no where near Dijkstra's algorithm yet, and even if I am struggling with simple algorithms. I start to wonder, isn't this the case for pretty much everyone?

[zaphraud]

lol oops. the, uh, distance adding function isn't adding the distances. This is the kind of silly mistake you make when you're tired all the time. But, there it is. Heh.

[zaphraud]

For a more realistic data set, I used crossing from one end of a cube to the other. Then to make the problem solvable with an actual answer, I put dents in the cube by altering the numbers. Also, I know what to expect with a dented cube formerly of size 9: Less than 27 total! Here's the cube

1 0 0 0 3 2 3 5 -1 
2 9 0 0 3 1 4 6 -1
3 0 9 0 3 1 4 7 -1
4 7 8 1 3 2 3 8 -1
5 0 0 9 3 1 6 7 -1
6 9 0 9 3 2 5 8 -1
7 1 8 8 3 3 5 8 -1
8 9 9 9 3 4 6 7 -1

This rapidly revealed a major problem with my code - it happily took all the shortest paths and meandered around the edges of the cube.

I added a bunch more debugging statements to print values and as I was doing so, saw my error: I wasn't comparing total distances, just distances. Silly oversight really. The simply act of writing the code to print the total distances made it glaringly obvious I wasn't using them because it wasn't there for me to copy and paste into the cout statement :-)

Here's the current version:

#include <iostream>
#include <fstream>
#include <math.h>

using std::cout;
using std::ifstream;

#define NUMPOINTS 100 //a maximum
#define DIMENTIONS 3 //this isn't really flexible since the file format is hard coded. oh well.
#define MAXCONNECTIONS 12
#define DATAFILE "connections.txt"
//Format: 
//pointID, point x, point y, point z, number of connections, (connected id 1, connected id 2, ...), -1
//the -1 is a terminator that lets me find my typos. I hope. Since I'm not coding any other sanity checking.
//the first point is the origin
//the last point is the destination

//-----The main data set is globally available-------
float points[NUMPOINTS][DIMENTIONS];//3 dimensions worth of coordinates
float totaldistance[NUMPOINTS]; //total distance from start
bool visited[NUMPOINTS]; // if set, point does not need calculating again
int connectedpoints[NUMPOINTS][MAXCONNECTIONS]; //list of connected points, possibly complete.
int arrivedfrom[NUMPOINTS]; //set when a point's total distance is altered. indicates what node was being visited when 
//----------------------------------------------------

float getdistance(int p1, int p2);
int closestpoint();
void calcneighbors(int p1); //update distances to all unvisited neighbors

int main () {
	int p1=0, p2=0, pmax=0, c=0, nc=0, z=0, error=0;
	int firstpoint=0, lastpoint=0, steps=0;
	float x=0, y=0, d=0;

//clean the arrays
	for (p1=0; p1<NUMPOINTS; p1++) {
		visited[p1]=0;
		arrivedfrom[p1]=0;
		totaldistance[p1]=0;
		for (c=0; c<DIMENTIONS; c++) {
			points[p1][c]=0;
			}		
		for (c=0; c<MAXCONNECTIONS; c++) {
			connectedpoints[p1][c]=0;
			}
		}
	p1=0; c=0; //reinitialize after flush

//read file of points and connections
	ifstream file(DATAFILE);
	while(!file.eof() && (error==0)) {
		file >> p1; 
		if (firstpoint==0) {
			firstpoint=p1; //remember the first point read
			}
		lastpoint=p1; //remember the last point read
		file >> points[p1][0] >> points[p1][1] >> points[p1][2];
		file >> nc;
		for (c=0; c<nc; c++) {
			file >> connectedpoints[p1][c];
			}
		file >> z;
		if (z != -1) {
			cout <<"\n\n HUGE ERROR! p1=" << p1 << " nc=" << nc <<" !!!\n\n";
			error=1;
			}
		}
	file.close();
//DEBUG:
	cout << "First point ID " << firstpoint << "\n" ;
	cout << "Last point ID " << lastpoint << "\n" ;
	cout << "Distance as bird flies: " << getdistance(firstpoint,lastpoint) << "\n";
	cout << "Closest unvisited point: " << closestpoint() << "\n";
//END DEBUG

//BEGIN JOURNEY
	p1=firstpoint;
	calcneighbors(p1);

	while (p1!=lastpoint) {
		visited[p1]=1; //mark current point
		p2=closestpoint();
		cout << "Visited " << p1 << ". Closest unvisited point: " << p2 << " trip distance of " << totaldistance[p2] << "\n"; //DEBUG
		p1=p2; //go to that point next
		calcneighbors(p1);
		}

//SHOW ME THE WAY HOME (the solution)
	p1=lastpoint;
	cout << "Path back: ";
	while (p1 != firstpoint) {
		cout << p1 << " - ";
		p1=arrivedfrom[p1];
		steps++;
		}
	cout << p1 << ".\n";
	cout << "Total distance of " << totaldistance[lastpoint] << " with " << steps << " steps.\n";
	}
//
//return distance between two points
//
float getdistance(int p1, int p2) { 
	float squared=0;
	int d=0;
	for (d=0; d<DIMENTIONS; d++) {
		squared+=(points[p1][d]-points[p2][d])*(points[p1][d]-points[p2][d]);
		}
	return sqrt(squared);
	}

//
//return closest unvisited point
//
int closestpoint() {
	int p1=0, point=0;
	float d=0;
	for (p1=0; p1 < NUMPOINTS ; p1++) {
		if (visited[p1]==0 && totaldistance[p1]!=0) { //ignore uncalculated
			if (totaldistance[p1] < d || d==0) { //first found or smaller distance
				d=totaldistance[p1];
				point=p1;
				}
			}
		}
	return point;
	}

//
// Update distances to connected and unvisited points
//
void calcneighbors (int p1) {
	int p2=0, c=0;
	float d=0;
	while (connectedpoints[p1][c]!=0) {
		p2=connectedpoints[p1][c];
		cout << "looking at " << p2 << " from " << p1 << "\n"; //DEBUG
		if (visited[p2]==0) {
			d=getdistance (p1,p2);
			cout << "from " << p1 << " to " << p2 << " is " << d << " calculated.\n";  //DEBUG. OH OOOPS...
			if (d + totaldistance[p1] < totaldistance[p2] || totaldistance[p2]==0) { //if less than or if first time
				cout << totaldistance[p2] << " is more than " << totaldistance[p1] << " plus " << d << " (or first time)\n";
				totaldistance[p2] = d + totaldistance[p1]; //update distance
				arrivedfrom[p2] = p1; //leave a hans-n-gretel breadcrumb
				cout << p1 << " " << p2 << " " << d << " updated\n";  //DEBUG
				}
			}
		c++;
		}
	}

First point ID 1
Last point ID 8
Distance as bird flies: 15.5885
Closest unvisited point: 0
looking at 2 from 1
from 1 to 2 is 9 calculated.
0 is more than 0 plus 9 (or first time)
1 2 9 updated
looking at 3 from 1
from 1 to 3 is 9 calculated.
0 is more than 0 plus 9 (or first time)
1 3 9 updated
looking at 5 from 1
from 1 to 5 is 9 calculated.
0 is more than 0 plus 9 (or first time)
1 5 9 updated
Visited 1. Closest unvisited point: 2 trip distance of 9
looking at 1 from 2
looking at 4 from 2
from 2 to 4 is 8.30662 calculated.
0 is more than 9 plus 8.30662 (or first time)
2 4 8.30662 updated
looking at 6 from 2
from 2 to 6 is 9 calculated.
0 is more than 9 plus 9 (or first time)
2 6 9 updated
Visited 2. Closest unvisited point: 3 trip distance of 9
looking at 1 from 3
looking at 4 from 3
from 3 to 4 is 7.14143 calculated.
17.3066 is more than 9 plus 7.14143 (or first time)
3 4 7.14143 updated
looking at 7 from 3
from 3 to 7 is 8.12404 calculated.
0 is more than 9 plus 8.12404 (or first time)
3 7 8.12404 updated
Visited 3. Closest unvisited point: 5 trip distance of 9
looking at 1 from 5
looking at 6 from 5
from 5 to 6 is 9 calculated.
looking at 7 from 5
from 5 to 7 is 8.12404 calculated.
Visited 5. Closest unvisited point: 4 trip distance of 16.1414
looking at 2 from 4
looking at 3 from 4
looking at 8 from 4
from 4 to 8 is 8.30662 calculated.
0 is more than 16.1414 plus 8.30662 (or first time)
4 8 8.30662 updated
Visited 4. Closest unvisited point: 7 trip distance of 17.124
looking at 3 from 7
looking at 5 from 7
looking at 8 from 7
from 7 to 8 is 8.12404 calculated.
Visited 7. Closest unvisited point: 6 trip distance of 18
looking at 2 from 6
looking at 5 from 6
looking at 8 from 6
from 6 to 8 is 9 calculated.
Visited 6. Closest unvisited point: 8 trip distance of 24.4481
looking at 4 from 8
looking at 6 from 8
looking at 7 from 8
Path back: 8 - 4 - 3 - 1.
Total distance of 24.4481 with 3 steps.

I think it works now. It found the biggest dent and took that path.

[zaphraud]

Anyone wanna buy my a copy of visual C so I can have a real debugger? :-)

[Repeater]

You can try the free version. To a very large degree, it's the same as the one you pay for.

https://www.visualstudio.com/vs/express/

[zaphraud]

Ooh thanks. But first I gotta get that SSD. Only 8 gigs left on the laptop. Soon...