Find shortest paths in a matrix using Dijkstra's algorithm

Question

The problem is as follows:

I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths can there be in such a matrix, starting on the right above the castle and terminating on the right below the castle.

I proceed as such:

1. I search for a start field and target field, if none then there is no path.
2. If I find them I start Dijkstra search for the shortest path.
3. If I find a path then mark it as impassable.
4. Then start again searching for start and target field.

The problem I have is with the performance as it's slow for a large-size matrix. How can I improve that?

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;
constexpr int maxVal = 100000;
using pii = std::pair<int,int>;
using ppi = std::pair<pii,int>;


struct compare
{
    int operator()( const ppi& p1, const ppi &p2)
    {
        return p1.second > p2.second;
    }
};

int Dijkstra(vector<vector<int>> &graph,  int height, int width, pii source, pii target)
{

    vector <int> dist(height*width, maxVal);
    vector <pii> prev(width*height);
    vector <vector<int>> cost(height,(vector<int> (width,1)));
    //possible moves from a field
    vector<pii> dmove;
    dmove.push_back(pii(0, -1));
    dmove.push_back(pii(0, +1));
    dmove.push_back(pii(-1, 0));
    dmove.push_back(pii(+1, 0));

    vector<bool> visited(height*width, false);

    priority_queue < ppi, vector<ppi>, compare> priorityQueue;

    dist[source.first * width + source.second]=0;

    priorityQueue.push(ppi(source, dist[source.first * width + source.second]));

    visited[source.first * width + source.second] = true;

    while(!priorityQueue.empty())
    {
        pii current = priorityQueue.top().first;
        priorityQueue.pop();
        //checking possible moves from the current field
        for (vector<pii>::iterator it = dmove.begin(); it != dmove.end(); ++it)
        {
            {
                int y = current.first + it->first;
                int x = current.second + it->second;
                int index = current.first * width + current.second;//indexing from 2d vector to 1d

                //check if field is valid
                if (x >= 0 && x < width && y >= 0 && y < height && graph[y][x] != 1 && dist[index]+1 < dist[y*width+x] && !visited[y*width+x])
                {
                    dist[y*width+x]=dist[index]+1;

                    prev[y*width+x]=pii(current.first, current.second);

                    priorityQueue.push(ppi(pii(y,x),dist[y*width+x]));

                    visited[y*width+x] = true;
                }
            }
        }
    }

    pii traceBack = target;

    //set the path already traversed to impassable
    if(dist[traceBack.first * width + traceBack.second]!= maxVal)
    {
        graph[traceBack.first][traceBack.second]=1;
        do
        {
            traceBack = prev[traceBack.first * width + traceBack.second];
            graph[traceBack.first][traceBack.second]=1;

        }
        while(traceBack!=source);
        return 1;//path found
    }


    return 0;//no path found
}

pii findTarget(vector<vector<int>> field, int height, int width, int loc)
{
     //search for the next free field under the castle at the right of the matrix
    for(int a=loc; a<=height; a++)
    {
        if(field[a][width]!=1)
        {
            return pii(a,width) ;
        }
    }
    return pii(-1,-1);//no target found
}

pii findStart(vector<vector<int>> field, int height, int width, int loc)
{
     //search for the next free field under the castle at the right of the matrix
    for(int a=loc; a>=0; a--)
    {
        if(field[a][width]!=1)
        {
            return pii(a,width);
        }
    }
    return pii(-1,-1);//no source found
}

int main()
{
    int cases;
    int width, height, nrOfObjects;//field size
    int cx, cy, castleWidth, castleHeight;//castle coordinates
    int xi, yi, widthi, heighti;//impassable terrain

    cin>>cases;

    for(int c=1; c<=cases; c++)
    {
        cin>>width>>height>>nrOfObjects;

        vector<vector<int> > field(height,(vector<int> (width,0)));

        cin>>cx>>cy>>castleWidth>>castleHeight;

        for(int a=0; a<castleHeight; a++)
        {
            for(int b=0; b<castleWidth; b++)
            {
                field[cy+a-1][cx+b-1] = 1;
            }
        }

        for(int i = 0; i<nrOfObjects; i++)
        {
            cin>>xi>>yi>>widthi>>heighti;

            for(int a=0; a<heighti; a++)//set the terrain as obstacle
            {
                for(int b=0; b<widthi; b++)
                {
                    field[yi+a-1][xi+b-1] = 1;
                }
            }
        }

        pii start, target;
        int scouts=0, i=0;

        while(true)
        {
            //search for the start and target node in the field
            start = findStart(field, height-1, width-1, cy-1-i);
            target= findTarget(field, height-1, width-1, cy+castleHeight-1+i);
            //if there is no start or target stop the search
            if(!(target.first==-1 || start.first == -1) )
            {
                i++;//so the search for start and target field dont start from the same spot
                scouts += Dijkstra(field, height, width, start, target);
            }
            else break;

        }

        printf("Case #%d: %d\n", c, scouts);

    }
    return 0;
}

Answer 1

Dijkstras's algorithm

Your implementation is wrong.

1. You expand all the points on the graph.
2. You mark and check for visited is in the wrong place

It should look like this

// Not tested so it may contain a few syntax errors.
vector<pii> const dmove {{0, -1}, {0, +1}, {-1, 0}, {+1, 0}};
struct Frontier
{
    pii               point;
    int               distance;
    std::vector<pii>  path;
};

std::vector<pii> Dijkstra(vector<vector<int>> &graph, int height, int width, pii source, pii target)
{
    using  DijkstraPriority = priority_queue<Frontier, vector<Frontier>, compare>;

    vector<int>      visited(height*width, 0);
    DijkstraPriority frontierList;

    frontierList.push_back({source, 0, {}});
    while(!frontierList.empty())
    {
        pii current = frontierList.top();
        frontierList.pop();

        // If you have reached the target then you now
        // have the shortest path to the target. So exit.
        if (current.point == target) {
            current.path.push_back(current.point);
            return current.path;
        }

        // We have already got the shortest route to this point.
        // So we can ignore this item.
        if (visited[current.point.x * width + current.point.y]) {
            continue;
        }

        // This is the shortest route to this point.
        // So mark it as visited and get the data about the point.
        // for use in marking any children.
        visited[current.point.x * width + current.point.y] = true;
        auto currentPath = current.path;
        auto currentDist = current.dist;
        currentPath.push_back(current.point);

        // Loop over all possible exit paths.
        for (auto it = dmove.begin(); it != dmove.end(); ++it) 
        {
            // Get all valid points inside the grid.
            int y = current.point.x + it->first;
            int x = current.point.y + it->second;
            if (x <= 0 || x >= width || y < 0 || y >= height) {
                continue;
            }

            //check if field is valid if so add it to the frontier
            if (graph[y][x] != 1) {
                frontierList.push({{x,y}, currentDist + 1, currentPath});
            }
        }
    }
    // return empty path when non exists.
    return {};
}

Interface

Your encapsulation of the graph is terrible.

vector<vector<int>> &graph, int height, int widt

Basically you have to pass three values to define the graph. If any of the values are accidentally wrong then things go wrong. Also you are requiring the algorithm to understand the internal structure of your vector<vector<int>> You have to know that 1 means blocked and any other value means unblocked.

Why not wrap a graph up in its own class so that all this information is encapsulated. You could even put together a better interface to find the distance to the next point. Say next point north (then you can scan north and ignore all points that don't have a junction).

Code Review

Stop doing this:

using namespace std;

See: Why is “using namespace std” in C++ considered bad practice?.

Its fine for 10 line pieces of code. But its a bad habit that will come to bite you in the but. So prefer not to use it even in your 10 line pieces of short code so you don't get into the habit and accidentally do it with larger pieces of code.

Lambda

Sure this works.

struct compare
{
    int operator()( const ppi& p1, const ppi &p2)
    {
        return p1.second > p2.second;
    }
};

But you can use a lambda to do it in place with modern C++. This prevents reviewers needing to search the code for the comparison operator.

vector

Avoid vector bool. It is actually a specialization of vector optimized for size. As a result it is very inefficient in terms of speed.

    vector<bool> visited(height*width, false);

Use auto when you don't care about the type.

        for (vector<pii>::iterator it = dmove.begin(); it != dmove.end(); ++it)

Iterators are one of those types where you don't care about the exact type. Just that it is an iterator of some description.

One Variable per line

Also initialize on declaration and declare them as close to the point of first use as you can.

    int width, height, nrOfObjects;//field size
    int cx, cy, castleWidth, castleHeight;//castle coordinates
    int xi, yi, widthi, heighti;//impassable terrain

A lot of these garbage values could be removed if you had encapsulated your graph.

White Space For Readability

        cin>>width>>height>>nrOfObjects;

        // Usually I see this in code.
        cin >> width >> height >> nrOfObjects;


        field[yi+a-1][xi+b-1] = 1;

        // Same in expressions.
        field[yi + a + 1][xi + b - 1] = 1;

Don't need space between '> >' on templates anymore.

        vector<vector<int> > field(height,(vector<int> (width,0)));