'Fake Code'

#include <iostream>
#include <stack>    //For tracing paths at the end
#define NAN 999;    //To mark nodes that don't directly connect

using namespace std;

int current, mindex;
int distanceArray[7][7]; //2D array to hold the distances from each point to all others
int d[6]; //Single distance array from source to points
int p[6];
int copyD[6]; //Single array to keep the predecessors
int order[6];


void tracePath(int x)
{
    //Stack to hold predecessors
    stack<int> path;

    cout<<d[x]<<": ";
    bool done = false;
    int ps = x;
    while(!done)
    {
        path.push(ps);
        ps=p[ps];

        if(ps==1)
        {
            path.push(ps);
            done = true;
        }
    }
    while(!path.empty())
    {
        int j= path.top();
        path.pop();
        if(path.empty())
            cout<<j;
        else
            cout<<j<<"->";
    }
    cout<<endl;

}


void output()
{

    //Create array with the shortest paths in order
    //array stores the reference to end node so we can get predecessor
    //Set order array to distance array

/*  cout<<"Starting array: "<<endl;
    for (int i = 1; i<7; i++)
    {
        copyD[i] = d[i];
        cout<<copyD[i]<<" ";
    }
    cout<<endl; */

    int theMin = 1;

    for(int c=1; c<7; c++)
    {
        for(int v=1; v<7; v++)
        {
            if (copyD[theMin] > copyD[v])
            {
                theMin=v;
                //cout<<"New min is: "<<v<<endl;
            }

        }//End inside for

        //Change the value of min to not catch it in next loops
        copyD[theMin]=999;
        //Store index of the min in our order array
        order[c]=theMin;

        /*
        cout<<"New array: ";
        for (int i = 1; i<7; i++)
        {
            cout<<copyD[i]<<" ";
        }
        cout<<endl;

        */
    /*  cout<<"Order array: ";
        for (int i = 1; i<7; i++)
        {
            cout<<order[i]<<" ";
        }
        cout<<endl; */

        //Now we have order array of shortest paths
        //Take each path, put it's predecessors in stack to trace
        //and print distance followed by path



    } //End outside for

    for (int i=1; i<7; i++)
            tracePath(order[i]);




}



void printArray()
{


cout<<"Printing 2D array"<<endl;

for(int i=1; i < 7; i++)
{
    for (int j=1; j < 7; j++)
    {   if(distanceArray[i][j]==-99)
            cout<<" - ";
        else
            cout<<distanceArray[i][j]<<" ";
        if(j==6)
            cout<<endl;
    }
}

cout<<"Printing Distances:"<<endl;

for(int i=1; i<7; i++)
    cout<<"Distance from 1 to "<<i<<" is "<<d[i]<<endl;

cout<<"Printing predecessors: "<<endl;

for(int i=1; i<7; i++)
    cout<<"Predecessor of "<<i<<" is "<<p[i]<<endl;


}

void Initialize()
{
        /*
    Distances
1->2 = 10
1->4 = 30
1->5 = 100
2->3 = 50
3->5 = 10
3->6 = 5
4->6 = 15
4->3 = 20
5->4 = 60
*/

//Hardcoding the test case into distanceArray
//First make them all infinity
//When they are visited, they are marked with a different number

for(int i=1; i < 7; i++)
{
    d[i]=NAN;   //All distances start high
    p[i]=0;     //No predecessors at first

    for (int j=0; j < 7; j++)
            distanceArray[i][j]=NAN;
}

    d[1]=0; //Source to source
    p[1]=1;

//Now overwrite nodes that connect with the weights of their edges
distanceArray[1][2]=10;
distanceArray[1][4]=30;
distanceArray[1][5]=100;
distanceArray[2][3]=50;
distanceArray[3][5]=10;
distanceArray[3][6]=5;
distanceArray[4][6]=15;
distanceArray[4][3]=20;
distanceArray[5][4]=60;

}

void dijkstra() {

    //Create Map
    Initialize();

    for(int i=0; i<5; i++)
    {

        current=1;

        while(current!=6)
        {
            //Iterate through and update distances/predecessors
            //For loopt go through columns, while current iterates rows
            for(int j=1; j<7; j++)
            {
                //Check if distance from current to this node is less than
                //distance already stored in d[j] + weight of edge

                if(distanceArray[current][j]+d[current]<d[j])
                {
                    //cout<<"Previous distance to "<<j<<" was "<<d[j]<<" from "<<p[j]<<endl;
                    //cout<<"New smaller distance is "<<distanceArray[current][j]+d[current]<<" from "<<current<<endl;
                    //Update distance
                    d[j] = distanceArray[current][j]+d[current];
                    //Update p
                    p[j] = current;
                }
            }
            //Go to next row in distanceArray[][]
            current++;
        } //End while


    } //End for
    //printArray();

}



int main(int argc, char *argv[]) {

    dijkstra();
    output();
    return 0;
}