Return to Answer

##Comma operator?##

I don't like how you use of the comma operator to put multiple statements on one line. It makes it harder to see where each statement starts and ends. For example:

 if (distance[u] + G[u][i] < distance[i])
 {
 distance[i] = distance[u] + G[u][i], parent[i] = u + 1;
 }

At first glance it looks like you are simply assigning something to distance[i]. But if you expand it:

 if (distance[u] + G[u][i] < distance[i])
 {
 distance[i] = distance[u] + G[u][i];
 parent[i] = u + 1;
 }

you could more easily see that both distance[i] and parent[i] were being modified.

Also, if you really wanted to only use one line, you could use a semicolon instead of a comma. Although I see that in the original code listing there were no curly braces for the if statement so you needed to use the comma operator to keep everything in one statement.

##Efficiency##

If this is just a small demonstration problem with a limit of 20 vertices, there's no problem with using arrays and a matrix. The code is definitely much simpler than if you used lists or a heap.

For a larger problem set, many graphs are described by a small list of edges instead of a matrix. So for example, with your program, if you increased the graph size to 1000 vertices, you would need to input 1000000 matrix elements, even if the graph only had 2000 edges. That's why many graph algorithms use an adjacency list representation instead of a matrix representation.

As far as global variables, they are a sign of a "toy program". A real program would keep the graph and algorithm state in some kind of local structure, to be passed around to the helper functions. Otherwise, you could only ever have one graph in your entire program.

Comma operator?

I don't like how you use of the comma operator to put multiple statements on one line. It makes it harder to see where each statement starts and ends. For example:

 if (distance[u] + G[u][i] < distance[i])
 {
 distance[i] = distance[u] + G[u][i], parent[i] = u + 1;
 }

At first glance it looks like you are simply assigning something to distance[i]. But if you expand it:

 if (distance[u] + G[u][i] < distance[i])
 {
 distance[i] = distance[u] + G[u][i];
 parent[i] = u + 1;
 }

you could more easily see that both distance[i] and parent[i] were being modified.

Also, if you really wanted to only use one line, you could use a semicolon instead of a comma. Although I see that in the original code listing there were no curly braces for the if statement so you needed to use the comma operator to keep everything in one statement.

Efficiency

If this is just a small demonstration problem with a limit of 20 vertices, there's no problem with using arrays and a matrix. The code is definitely much simpler than if you used lists or a heap.

For a larger problem set, many graphs are described by a small list of edges instead of a matrix. So for example, with your program, if you increased the graph size to 1000 vertices, you would need to input 1000000 matrix elements, even if the graph only had 2000 edges. That's why many graph algorithms use an adjacency list representation instead of a matrix representation.

As far as global variables, they are a sign of a "toy program". A real program would keep the graph and algorithm state in some kind of local structure, to be passed around to the helper functions. Otherwise, you could only ever have one graph in your entire program.