Results 1 to 2 of 2

Thread: cpp dijkstra weighted graph optimize

  1. #1
    Join Date
    Feb 2012
    Location
    Wonderland
    Posts
    1,988
    Mentioned
    41 Post(s)
    Quoted
    272 Post(s)

    Default cpp dijkstra weighted graph optimize

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

    --> How to ease loop operations? (less = good)
    Code:
    // 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

  2. #2
    Join Date
    Feb 2011
    Location
    The Future.
    Posts
    5,600
    Mentioned
    396 Post(s)
    Quoted
    1598 Post(s)

    Default

    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.
    Last edited by Brandon; 11-01-2014 at 02:15 PM.
    I am Ggzz..
    Hackintosher

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •