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;
}