0

I think I am comparing something incorrectly since it does take in my input and tells me no shortest path.. here is example input and output...
5
7
0 1 1
0 2 2
1 3 6
1 4 4
2 3 5
2 4 7
3 4 3

you would output Shortest path found is 0-1-4-3-2.
atm my code outputs 0-1-4-0-0
here is my code...

#include <iostream>

using namespace std;

int main()
{
int E, N, node1, node2, weight, smallestW=NULL, smallestN=NULL;
int matrix[10][10] = {0};
int marked[10] = {NULL};

cout << "enter number of nodes\n";
cin >> N;
cout << "enter number of edges\n";
cin >> E;

cout << "enter two connected vertices and their weight\n";
for(int w = 0; w < E; w++)
{
    cin >> node1 >> node2 >> weight;
    matrix[node1][node2] = weight;
    matrix[node2][node1] = weight;
}

marked[0] = 0;
int i = 0;
int j = 0;
int count = 1;
bool end = false;
bool noSolution = false;

while(end == false)
{
    if(matrix[marked[i]][j] > 0 && smallestW == NULL)
    {
        smallestW = matrix[marked[i]][j];
        smallestN = j;
    }
    else if(matrix[marked[i]][j] < smallestW && matrix[marked[i]][j] != 0)
    {
        smallestW = matrix[marked[i]][j];
        smallestN = j;
    }
    j++;
    if(j > N && smallestW > 0)
    {
        marked[count] = smallestN;//adding node to solution
        count ++;
        for(int q = 0; q < 10; q++)
        {
            matrix[i][q] = 0;//making weight 0, so not reused
            //matrix[q][i] = 0;//making weight 0, so not reused
        }
        i = smallestN;//now matrix is starting with the smallest node
        j = 1;//restart with first one, not zero since we started with it
        smallestN = NULL;
        smallestW = NULL;
    }
    else if(j > N && smallestW == NULL)
    {
        end = true;
        if(marked[N-1]==NULL)
            noSolution = true;
    }
}

// if(noSolution)
// cout << "No Path can be found";
// else
// {
cout << "Shortest path found is ";
for(int i = 0; i < N; i ++)
cout << marked[i];
//}

return 0;

}

Edited by jigglymig

1
Contributor
1
Reply
2
Views
4 Years
Discussion Span
Last Post by jigglymig
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.