Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am solving one problem with shortest path algorithm, but it is too slow.

The problem is that I have N points and these can be connected only if the distance between them is smaller or equal than the D. I have a start index and finish(ciel in code) index and have to return the shortest path in double format.

Firstly I thought that the sqrt is too slow, but when I changed it, it was still too slow. I am backtracking the distance and using sqrt just there for better speed, but it is too slow. I have used a priority queue. For more information, the input consists of the X and Y of the points , D maximal distance to make edge, start index and finish index. There can be max 1000 points.

// The main problem is that, it crashes of memory, I do not think I use so much of it but, it crashes from bad_alloc

Here is my code.

Are there any ways of making it faster, please?

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <utility>

using namespace std;

const int MAX = 1001;
const int INF = 1e9;

std::vector< std::pair<int, int> > edges[MAX]; // hrany a vzdialenosti medzi bodmi a hranami
int N; // pocet vrcholov
int start, ciel; // start a ciel index

double dijkstra() {
    int vis[N]; // pocet navstiveni daneho bodu
    int prevNodes[N][2];
    for(int i=0;i < N;i++)
        prevNodes[i][1] = INF;

    std::priority_queue< std::pair<int, int> > heap; // halda
    for(int i = 0; i < N; i++) vis[i] = 0;
    heap.push(pair<int, int>(0, start));
    while(!heap.empty())
    {
        pair<int, int> min = heap.top(); // vybratie dalsieho
        heap.pop(); // vyhodenie pozreteho
        min.first *= -1.0; // kvoli spravnemu fungovaniu priority
        int v = min.second; // len pre oko

        vis[v]++;
        if (v == ciel && vis[v] == 1)
        {
            double d = 0.0; 

            int prevIndex = ciel, nextIndex = prevNodes[ciel][0]; 

            while(1)
            {

                for(int j=0;j < edges[nextIndex].size();j++)
                    if(edges[nextIndex][j].first == prevIndex)
                    {

                        d += sqrt(double( edges[nextIndex][j].second ));
                        break;
                    }

                prevIndex = nextIndex; // posunutie
                if(nextIndex == start) // ak sme uz na zaciatku
                    break;
                else
                    nextIndex = prevNodes[nextIndex][0];// posun dalej
            }
            return d; // najkratsia cesta
        }

        for (int i = 0; i < (int) edges[v].size(); i++)
        {
            if (vis[edges[v][i].first] < 1)
            {
                if(prevNodes[edges[v][i].first][1] > min.first + edges[v][i].second)
                {
                    prevNodes[edges[v][i].first][0] = min.second;

                    prevNodes[edges[v][i].first][1] = min.first + edges[v][i].second;
                }
                heap.push(pair<int, int>(-(min.first + edges[v][i].second), edges[v][i].first)); 
            }
        }
    }
    return -1;
}

int main()
{
    int X;
    scanf("%d",&X);
    double answers[X];
    for(int i=0;i < X;i++)
    {
        int D, sIndex, eIndex; // N je globalne
        scanf("%d %d", &N, &D); // N
        int DD = D * D;
        for(int j=0;j < N;j++)
            edges[j].clear();

        int V[N][2]; // N
        int x, y;
        for(int k=0;k < N;k++) // N
        {
            scanf("%d %d", &x, &y);
            V[k][0] = x;
            V[k][1] = y;
        }

        for(int a=0;a < N;a++)
            for(int b=0;b < N;b++)
            {

                int v = (((V[a][0] - V[b][0]) * (V[a][0] - V[b][0]) +
                                (V[a][1] - V[b][1]) * (V[a][1] - V[b][1])));
                if(v > DD)
                    continue;
                else
                {
                    edges[a].push_back(pair<int, int>(b, v));
                    edges[b].push_back(pair<int, int>(a, v));
                }
            }

        scanf("%d %d", &start, &ciel);
        start--;
        ciel--;
        double dijLen = dijkstra();
        if(dijLen < 0)
            answers[i] = -1;
        else
            answers[i] = dijLen;
    }
    for(int i=0;i < X;i++)
        if(answers[i] < 0)
            printf("Plan B\n");
        else
            printf("%.2f\n", answers[i]);

    return 0;
}
share|improve this question

closed as off-topic by ChrisW, syb0rg, Jeff Vanzella, Mat's Mug, Nikita Brizhak Feb 12 at 6:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – ChrisW, syb0rg, Jeff Vanzella, Mat's Mug, Nikita Brizhak
If this question can be reworded to fit the rules in the help center, please edit the question.

    
I cannot quite tell where you may be getting bad_alloc. You may need to use breakpoints in various places to determine this, or trace the stack. You don't use new or malloc anywhere, so one of the storage container operations may be throwing. The nested loops in main() look suspicious, but I cannot tell for sure. –  Jamal Feb 10 at 19:06
    
Have you managed to get a result for any input? When does it start to crash? –  Simon André Forsberg Feb 10 at 19:27
    
    
Post rolled back. Please don't update the original code from answers; that will invalidate them. Follow-up reviews should be done in a new question. If the code is not working, it should instead be posted on Stack Overflow. –  Jamal Feb 11 at 19:32

3 Answers 3

up vote 12 down vote accepted

Couple things that I see that would make this a lot more efficient:

First, you don't need to determine all of the valid edges before you start the Dijkstra algorithm. Assuming that the only constraint on whether two points have a valid edge is that "the distance between them is smaller or equal than the D", there is no reason to determine the complete connection tree before entering the path search. The loop in main is essentially just computing the distance from every node to every other node, with up to 1000 nodes. This gives the maximum number of distance calculations as 1000 factorial. Since the weight for any given edge is only the distance between them, it would be much better to just assume that all nodes are connected and reject edges inside the Dijkstra algorithm if the edge distance is greater than D.

Second, you don't need to test all of the resulting edges within the Dijkstra algorithm. You can cut down on your set of edges to weigh by filtering them each time you take a step through the tree, and only calculate distances (and thus edge weighting) for nodes that are possible edges. You only have to calculate distances between any two nodes where both x[a] - x[b] and y[a] - y[b] are less than D. Taking this a step further, you only have to calculate square roots on the set of nodes where delta x plus delta y are equal and are the lowest value. This takes the vast majority of the math that is currently being performed with relatively expensive multiply and root calls and replaces it with cheap additions and subtractions.

Third, depending on the distribution of the input set and the method you chose for rejecting edges in the Dijkstra algorithm, it might be faster to sort the input set before you start. That way you can just ignore any indices that fall outside of your distance constraint from the current node. Even if you are only sorting by one of the coordinates, it gives a really easy way to identify edges that have a distance greater than D because you don't have to traverse the entire set of nodes each time you are applying edge weights.

share|improve this answer
    
I implemented the first and the third, but the heap sometimes ran out of memory with 1000 points, crashes, I checked it and it has about 67 000 000 items at the crash. –  user36546 Feb 11 at 19:29
    
Here is modified code, can you check it for logic errors due to wrong answer text please? pastebin.com/0WiuVCNM –  user36546 Feb 11 at 19:43
    
I tried the A* way because it was crashing due to heap overflow. Here it is pastebin.com/sNf1w55c , I am waiting response from judge because it cannot get compiled on their compiler. –  user36546 Feb 12 at 18:51
    
I fixed it, but now I am getting wrong answer again, can somebody check the code logic please? –  user36546 Feb 12 at 19:17

C++-specific:

  • You're mixing C and C++ libraries:

    • You already have <iostream>, so you don't need <stdio.h>.

      However, if you can only use printf and scanf for whatever reason, then remove <iostream>. Otherwise, just use std::cout and std::cin, and remove <stdio.h>.

    • The C++ library version of <stdlib.h> is <cstdlib>.

    • The C++ library version of <math.h> is <cmath>.

  • Global variables is bad practice:

    std::vector< std::pair<int, int> > edges[MAX];
    int N;
    int start, ciel;
    

    Prefer to pass these variables to functions as needed, or keep them in the one needed function. Having them global can introduce bugs, which will just make maintenance more difficult.

  • Although you're not doing everything in main() (which is good), you still seem to be doing quite a bit in it. If dijkstra() is supposed to handle most of the work, then you may need more functions to call from main(). It should not be doing the hard work; that's for the other functions.

    From a maintainability standpoint, also, this isn't the best approach. You should mostly be taking the initial input, give it to the function(s) to do the work, then receive and display the results.

  • This loop:

    for(int i=0;i < X;i++)
        if(answers[i] < 0)
            printf("Plan B\n");
        else
            printf("%.2f\n", answers[i]);
    

    should have curly braces:

    for(int i=0;i < X;i++)
    {
        if(answers[i] < 0)
            printf("Plan B\n");
        else
            printf("%.2f\n", answers[i]);
    }
    

Performance:

  • Part of your performance issue may have to do with the nested for-loops in main(). At the least, you'll have O(n2), which will already be quite large, depending on the number. You then have a loop outside of that, which will increase this complexity.

    Overall, you have many loops throughout the program, which, alongside the performance issue, could be an indication that your algorithm implementation in't ideal. You also don't use new or malloc anywhere, so one of the container operations may be throwing bad_alloc. You may need to use breakpoints to determine this, perhaps where you call push() and push_back().

share|improve this answer
    
I know about all these things, but when I am tweaking and playing with it I use some of them sometimes. –  user36546 Feb 10 at 18:45
1  
@user36546: If so, that should be stated in the explanation for the reviewers. –  Jamal Feb 10 at 18:50
2  
I do not think it has something to do with the real problem or its part. It is unimportant. –  user36546 Feb 10 at 19:12
3  
@user36546: True, but on Code Review, feedback on anything is fair game. Specific questions are still important, but they don't have to be the only things addressed. –  Jamal Feb 10 at 19:14
3  
@0A0D - See the help center for what is fair-game... it clearly says: 6. Do I want feedback about any or all facets of the code? –  rolfl Feb 11 at 17:59

Instead of checking:

distance < D // distance has sqrt calculations

try checking

(distance squared) < (D squared)

No sqrt is required, equivalent to your test case (i.e. no imaginary distances, right?).

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.