SRL Archive - C/C++ Help and Tutorials

Hello, I've code below, (yes, it's graph implementation, no queue/depth first/etc.)

–> How to ease loop operations? (less = good)

// pre-condition
/*
    struct graph {
        bool v; // visited
        int d; // distance
        int p; // path
    };
    int cost[size][size];
    int size;
    graph G[size][size];
*/

void dijkstra::find() {
	int target = 0;
	for (int ptA = 1; ptA <= size; ptA++) {
        for (int i = 1; i <= size; i++) {
            int low = 2147483647; // infinity
            for (int v = 1; v <= size; v++) {
                if (!G[ptA][v].v && G[ptA][v].d < low) {
                    target = v;
                    low = G[ptA][v].d;
                }
            }
            G[ptA][target].v = true;
            for (int w = 1; w <= size; w++) {
                if (!G[ptA][w].v && cost[target][w] != 2147483647) {
                        int curr = 0;
                        curr += G[ptA][target].d;
                        curr += cost[target][w];
                    if (G[ptA][w].d > curr) {
                        G[ptA][w].d = G[ptA][target].d + cost[target][w];
						G[ptA][w].p = target;
					}
				}
			}
		}
	}
}

Cheers,
Lj

There's no way to optimise out the second inner loop and that's because you depend on target to be at its maximum index when (G[ptA][v].v && G[ptA][v].d < low) is true.


You can get rid of a couple instructions by changing the outer loop to: for (int ptA = 1; ptA <= size * size; ++ptA) but then you'd have to make sure the array has index size * size.
If you don't trust compilers (like myself), you can change the v++ and w++ to ++v and ++w.

Change low to:

const static int max_int = std::numeric_limits<int>::max(); //called once. calculated at compile time. #include <limits>
int low = max_int; // infinity

because int isn't guaranteed to always be 4 bytes. Though.. it probably is in your compiler.

Then you can do: if (!G[ptA][v].v && cost[target][w] != max_int) { //use the max_int

Other than that, you'll have to change the design. The loops are tightly coupled.