A little bit of backstory - I got an internship at an engineering company to help design an automatic ground vehicle that would follow magnetic tape around a building. I’m designing the software, and obviously a challenge I had to tackle was how to find the shortest route from point 1 to point 7 or whatever.
Because of this challenge, I wrote a function to find a shortest route given a map of line segments, as opposed to a grid as this is most often done in. I pretty much check to find all line segments connected to a start point, and then check to see if the other end of the line segment is the end point. If it’s not, then rerun the program with the endpoints of the previous line segment as the new start points, and so on and so forth. As soon as you have a path from the initial start point to the end, compare the length to a global variable. If the path you found is shorter, replace it. This then finds all possible routes between your initial start point and your endpoint, and gives you the shortest.
HOWEVER, just about when i was done (like five lines left and some debugging) I found a thing called Dijkstras algorithm. I have tried reading about it over and over, but I cannot seem to grasp it 
does anyone here have knowledge enough about it to explain it in slightly layman terms for me to understand?
My curiosity right now is completely academic, as the speed at which its running (on a raspberry pi) and the size of the map (~30) it will likely be dealing with, means it can pre pocess every possible route in ~2.5 seconds. I’m simply interested for how I could have done better.
EDIT: I’m at school right now, and the firewall blocks github 
but as soon as I get home I’ll post the code. If you’re interested in checking it right now, it’s at http://github.com/infinity42/pathFinder
EDIT(2): Nevermind, I had it in an old e-mail! Also, if you check github it’s in a bad state because I’m changing it from c to c++. We’re doing the project in c but I prefer sandboxing in c++. here is my code:
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#define LINE_SEG 21
#define VERTEX 20
#define MX_LGTH_MP 1023
using namespace std;
int pDist = MX_LGTH_MP;
int pStep = 0;
int shortestPath[LINE_SEG] = {0};
struct location {
bool type; // true will be point, false is line
int location;
} currentLoc;
struct Route {
int initStart; //the initial start location. good for diagnostics
int endLoc; //the all holy end location. where you are going
int startLoc; //the current "start" location. used for which point you are considering yourself at
int path[1023]; //the path so far
int map[LINE_SEG][3]; //the map data pulled from map.csv
int pSum; //the total distance of this path so far
int step; //which step you are on now. Useful for attaining final path without non-zero check in whitespace
int pvPoint; //the last point visited. useful for just not going backwards and being dumb. like you
};
int pathFind(Route route)
{
bool notVisited = true;
for(int i = 0; i < LINE_SEG; i++)
{
if(route.map*[0] == route.startLoc && route.map*[1] != route.pvPoint)
{
for(int k = 0; k < route.step; k++)
{
if(route.path[k] == i)
{
notVisited = false;
}
}
if(notVisited)
{
if(route.map*[1] == route.endLoc)
{
route.path[route.step] = i;
route.step++;
route.pSum = route.pSum + route.map*[2];
if(route.pSum < pDist)
{
pDist = route.pSum;
pStep = route.step;
for(int s = 0; s < route.step; s++)
{
shortestPath[s] = route.path[s];
}
}
return route.step;
}
else
{
if (true)
{
Route newRoute = route;
newRoute.path[newRoute.step] = i;
newRoute.step++;
newRoute.pSum = newRoute.pSum + newRoute.map*[2];
newRoute.pvPoint = newRoute.map*[0];
newRoute.startLoc = route.map*[1];
pathFind(newRoute);
}
}
}
}
if(route.map*[1] == route.startLoc && route.map*[0] != route.pvPoint)
{
for(int k = 0; k < route.step; k++)
{
if(route.path[k] == i)
{
notVisited = false;
}
}
if(notVisited)
{
if(route.map*[0] == route.endLoc)
{
route.path[route.step] = i;
route.step++;
route.pSum = route.pSum + route.map*[2];
if(route.pSum < pDist)
{
pDist = route.pSum;
pStep = route.step;
for(int s = 0; s < route.step; s++)
{
shortestPath[s] = route.path[s];
}
}
return route.step;
}
else
{
if (true)
{
Route newRoute = route;
newRoute.path[newRoute.step] = i;
newRoute.step++;
newRoute.pSum = newRoute.pSum + newRoute.map*[2];
newRoute.pvPoint = newRoute.map*[1];
newRoute.startLoc = newRoute.map*[0];
pathFind(newRoute);
}
}
}
}
}
}
Route initRoute(int startLoc, int endLoc) {
Route blankRoute;
blankRoute.initStart = startLoc;
blankRoute.startLoc = startLoc;
blankRoute.endLoc = endLoc;
blankRoute.pSum = 0;
blankRoute.step = 0;
blankRoute.pvPoint = 99;
for(int i = 0; i<LINE_SEG; i++)
{
blankRoute.path* = 0;
}
int a;
const char* dataPointer;
string data;
ifstream map ("map.csv");
//reads out the two input number
for(int i = 0; i < LINE_SEG; i++)
{
for(int n = 0; n < 2; n++)
{
getline(map, data, ',');
dataPointer = data.c_str();
a = atoi(dataPointer);
blankRoute.map*[n] = a;
}
getline(map, data, '
');
dataPointer = data.c_str();
a = atoi(dataPointer);
blankRoute.map*[2] = a;
}
return blankRoute;
}
void findFastestPath(Route route) {
pathFind(route);
cout << route.initStart << ',' << route.endLoc << ',' << pDist << ',' << pStep << ',';
for(int i = 0; i < pStep; i++)
{
cout << shortestPath* << ' ';
}
cout << endl;
pDist = MX_LGTH_MP;
pStep = 0;
for(int i = 0; i < LINE_SEG; i++)
{
shortestPath* = 0;
}
}
/*
*Accepts two arguments, a start location and an end location
* runs off of an insanely basic map at the moment.
*/
int main(int argc, char* argv]) {
//each element of the argv array after zero is a space delimited
//input. this allows/forces you to input two integers and then have
//them stored. pretty cool amirite?
int initStart = atoi(argv[1]);
int endLoc = atoi(argv[2]);
Route route = initRoute(initStart, endLoc);
findFastestPath(route);
for(int stt = 1; stt < VERTEX+1; stt++)
{
for(int end = 1; end < VERTEX+1; end++)
{
route = initRoute(stt, end);
findFastestPath(route);
}
}
return 0;
}
