Warning: Long post
Your problem lies within your algorythm. Here is why:
Assuming each node has direct access to all nodes with a higher value, the number of calculations to perform a check of 300 nodes is huge. For example, the following is a simple table of only 10 nodes:
Code:
10
45
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
2 3 1
2 4 1
2 5 1
2 6 1
2 7 1
2 8 1
2 9 1
2 10 1
3 4 1
3 5 1
3 6 1
3 7 1
3 8 1
3 9 1
3 10 1
4 5 1
4 6 1
4 7 1
4 8 1
4 9 1
4 10 1
5 6 1
5 7 1
5 8 1
5 9 1
5 10 1
6 7 1
6 8 1
6 9 1
6 10 1
7 8 1
7 9 1
7 10 1
8 9 1
8 10 1
9 10 1
1 10
For the purpose of the discussion, I have set all "peso" values (third number of each data line) to 1, as the point is to discuss the number of calculations required to traverse every route. Using your program, I simply added a counter in it to see how many complete paths it found. I did this by having a counter called CountOfPaths, and incremented its value every time "if (source == sink)" became true. For the above input (10 nodes), it told me there were 256 paths available. To prove it was doing its job correctly, I also made your program print out the paths as it found them, here's was it output:
Code:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 9 10
1 2 3 4 5 6 7 10
1 2 3 4 5 6 8 9 10
1 2 3 4 5 6 8 10
1 2 3 4 5 6 9 10
1 2 3 4 5 6 10
1 2 3 4 5 7 8 9 10
1 2 3 4 5 7 8 10
1 2 3 4 5 7 9 10
1 2 3 4 5 7 10
1 2 3 4 5 8 9 10
1 2 3 4 5 8 10
1 2 3 4 5 9 10
1 2 3 4 5 10
1 2 3 4 6 7 8 9 10
1 2 3 4 6 7 8 10
1 2 3 4 6 7 9 10
1 2 3 4 6 7 10
1 2 3 4 6 8 9 10
1 2 3 4 6 8 10
1 2 3 4 6 9 10
1 2 3 4 6 10
1 2 3 4 7 8 9 10
1 2 3 4 7 8 10
1 2 3 4 7 9 10
1 2 3 4 7 10
1 2 3 4 8 9 10
1 2 3 4 8 10
1 2 3 4 9 10
1 2 3 4 10
1 2 3 5 6 7 8 9 10
1 2 3 5 6 7 8 10
1 2 3 5 6 7 9 10
1 2 3 5 6 7 10
1 2 3 5 6 8 9 10
1 2 3 5 6 8 10
1 2 3 5 6 9 10
1 2 3 5 6 10
1 2 3 5 7 8 9 10
1 2 3 5 7 8 10
1 2 3 5 7 9 10
1 2 3 5 7 10
1 2 3 5 8 9 10
1 2 3 5 8 10
1 2 3 5 9 10
1 2 3 5 10
1 2 3 6 7 8 9 10
1 2 3 6 7 8 10
1 2 3 6 7 9 10
1 2 3 6 7 10
1 2 3 6 8 9 10
1 2 3 6 8 10
1 2 3 6 9 10
1 2 3 6 10
1 2 3 7 8 9 10
1 2 3 7 8 10
1 2 3 7 9 10
1 2 3 7 10
1 2 3 8 9 10
1 2 3 8 10
1 2 3 9 10
1 2 3 10
1 2 4 5 6 7 8 9 10
1 2 4 5 6 7 8 10
1 2 4 5 6 7 9 10
1 2 4 5 6 7 10
1 2 4 5 6 8 9 10
1 2 4 5 6 8 10
1 2 4 5 6 9 10
1 2 4 5 6 10
1 2 4 5 7 8 9 10
1 2 4 5 7 8 10
1 2 4 5 7 9 10
1 2 4 5 7 10
1 2 4 5 8 9 10
1 2 4 5 8 10
1 2 4 5 9 10
1 2 4 5 10
1 2 4 6 7 8 9 10
1 2 4 6 7 8 10
1 2 4 6 7 9 10
1 2 4 6 7 10
1 2 4 6 8 9 10
1 2 4 6 8 10
1 2 4 6 9 10
1 2 4 6 10
1 2 4 7 8 9 10
1 2 4 7 8 10
1 2 4 7 9 10
1 2 4 7 10
1 2 4 8 9 10
1 2 4 8 10
1 2 4 9 10
1 2 4 10
1 2 5 6 7 8 9 10
1 2 5 6 7 8 10
1 2 5 6 7 9 10
1 2 5 6 7 10
1 2 5 6 8 9 10
1 2 5 6 8 10
1 2 5 6 9 10
1 2 5 6 10
1 2 5 7 8 9 10
1 2 5 7 8 10
1 2 5 7 9 10
1 2 5 7 10
1 2 5 8 9 10
1 2 5 8 10
1 2 5 9 10
1 2 5 10
1 2 6 7 8 9 10
1 2 6 7 8 10
1 2 6 7 9 10
1 2 6 7 10
1 2 6 8 9 10
1 2 6 8 10
1 2 6 9 10
1 2 6 10
1 2 7 8 9 10
1 2 7 8 10
1 2 7 9 10
1 2 7 10
1 2 8 9 10
1 2 8 10
1 2 9 10
1 2 10
1 3 4 5 6 7 8 9 10
1 3 4 5 6 7 8 10
1 3 4 5 6 7 9 10
1 3 4 5 6 7 10
1 3 4 5 6 8 9 10
1 3 4 5 6 8 10
1 3 4 5 6 9 10
1 3 4 5 6 10
1 3 4 5 7 8 9 10
1 3 4 5 7 8 10
1 3 4 5 7 9 10
1 3 4 5 7 10
1 3 4 5 8 9 10
1 3 4 5 8 10
1 3 4 5 9 10
1 3 4 5 10
1 3 4 6 7 8 9 10
1 3 4 6 7 8 10
1 3 4 6 7 9 10
1 3 4 6 7 10
1 3 4 6 8 9 10
1 3 4 6 8 10
1 3 4 6 9 10
1 3 4 6 10
1 3 4 7 8 9 10
1 3 4 7 8 10
1 3 4 7 9 10
1 3 4 7 10
1 3 4 8 9 10
1 3 4 8 10
1 3 4 9 10
1 3 4 10
1 3 5 6 7 8 9 10
1 3 5 6 7 8 10
1 3 5 6 7 9 10
1 3 5 6 7 10
1 3 5 6 8 9 10
1 3 5 6 8 10
1 3 5 6 9 10
1 3 5 6 10
1 3 5 7 8 9 10
1 3 5 7 8 10
1 3 5 7 9 10
1 3 5 7 10
1 3 5 8 9 10
1 3 5 8 10
1 3 5 9 10
1 3 5 10
1 3 6 7 8 9 10
1 3 6 7 8 10
1 3 6 7 9 10
1 3 6 7 10
1 3 6 8 9 10
1 3 6 8 10
1 3 6 9 10
1 3 6 10
1 3 7 8 9 10
1 3 7 8 10
1 3 7 9 10
1 3 7 10
1 3 8 9 10
1 3 8 10
1 3 9 10
1 3 10
1 4 5 6 7 8 9 10
1 4 5 6 7 8 10
1 4 5 6 7 9 10
1 4 5 6 7 10
1 4 5 6 8 9 10
1 4 5 6 8 10
1 4 5 6 9 10
1 4 5 6 10
1 4 5 7 8 9 10
1 4 5 7 8 10
1 4 5 7 9 10
1 4 5 7 10
1 4 5 8 9 10
1 4 5 8 10
1 4 5 9 10
1 4 5 10
1 4 6 7 8 9 10
1 4 6 7 8 10
1 4 6 7 9 10
1 4 6 7 10
1 4 6 8 9 10
1 4 6 8 10
1 4 6 9 10
1 4 6 10
1 4 7 8 9 10
1 4 7 8 10
1 4 7 9 10
1 4 7 10
1 4 8 9 10
1 4 8 10
1 4 9 10
1 4 10
1 5 6 7 8 9 10
1 5 6 7 8 10
1 5 6 7 9 10
1 5 6 7 10
1 5 6 8 9 10
1 5 6 8 10
1 5 6 9 10
1 5 6 10
1 5 7 8 9 10
1 5 7 8 10
1 5 7 9 10
1 5 7 10
1 5 8 9 10
1 5 8 10
1 5 9 10
1 5 10
1 6 7 8 9 10
1 6 7 8 10
1 6 7 9 10
1 6 7 10
1 6 8 9 10
1 6 8 10
1 6 9 10
1 6 10
1 7 8 9 10
1 7 8 10
1 7 9 10
1 7 10
1 8 9 10
1 8 10
1 9 10
1 10
256 complete paths
Now, changing the input slightly, I came up with the following figures for the number of possible routes based on the number of nodes:
Code:
Nodes Total Routes
10 256
15 8192
20 262144
25 8388608
26 16777216
27 33554432
28 67108864
29 134217728
(do you see a pattern?)
With only 28 nodes, your program took 26 seconds to run, with 29 nodes it took 50 seconds. In short, add one node, and you double the paths, and therefore the execution time. Now, imagine the number of routes when you have 300 nodes to work through (I suggest you work that number out). That is why your program is struggling.
How to fix this? Find a better algorythm, or make this one smarter. How you do that is for you to find out... (it's your homework, afterall ).
To assist me with this work, I wrote small program to generate the input files, you might find it useful:
Code:
/*
* This generates the input files
*/
#include <stdio.h>
#define MAX 29
int main(void)
{
int i, j;
printf ("%d\n", MAX);
for (i = MAX-1, j = 0; i; i--)
j += i;
printf ("%d\n", j);
for (i = 1; i < MAX; i++)
for (j = i+1; j <= MAX; j++)
printf ("%-4d %-4d 1\n", i, j);
printf ("%-4d %-4d\n", 1, MAX);
return 0;
}
One last thing, don't bump your threads on here. If and when people have answers to your questions, they will post them.