How to apply a flooding algothrim to find the optimal path between a specified source and destination location for a weighted 2D matrix

Question

I've been trying to implement a class which uses a flooding algorithm to generate a list of the indexes for the optimal path between a specified source and destination index.

Such as:

void Dijkstra::findShortestPath(uint sourceIndex, uint destIndex, std::vector<int> & optimalPath);

For example, given a 5x5 2d matrix, find the optimal path between between X and Y:

[1][1][1][1][1]
[1][1][10][10][1]
[X][1][10][Y][1]
[1][1][10][10][1]
[1][1][1][1][1]

Expected result:

start(10)->11->6->1->2->3->4->9->14->13

Where the above index values map to row and column indexes in the matrix:

index = numOfVertices * rowNumber + rowNumber

I have found several different variants, but no implementation yet which does the above.

This algorithim I'm currently trying to extend to this, I found here:

http://www.programming-techniques.com/2012/01/implementation-of-dijkstras-shortest.html?m=1

Though I do not see how a destination node can be specified here, so I am struggling to understand how I can extend this.

My version is below, compiles and runs fine, however you can only specify the source index in the setBoard() function.

Code:

#include <iostream>
#include "stdio.h"

using namespace std;
const int BOARD_SIZE = 5;
const int INFINITY = 999;

class Dijkstra {
private:
int adjMatrix[BOARD_SIZE][BOARD_SIZE];
int predecessor[BOARD_SIZE];
int distance[BOARD_SIZE];
bool mark[BOARD_SIZE];
int source;
int numOfVertices;
public:

int getIndex(int row, int col);

void setBoard();
/*
 * Function initialize initializes all the data members at the begining of
 * the execution. The distance between source to source is zero and all other
 * distances between source and vertices are infinity. The mark is initialized
 * to false and predecessor is initialized to -1
 */

void initialize();

/*
 * Function getClosestUnmarkedNode returns the node which is nearest from the
 * Predecessor marked node. If the node is already marked as visited, then it search
 * for another node.
 */

int getClosestUnmarkedNode();
/*
 * Function calculateDistance calculates the minimum distances from the source node to
 * Other node.
 */

void calculateDistance();
/*
 * Function output prints the results
 */

void output();
void printPath(int);
};

int Dijkstra::getIndex(int row, int col)
{
    return numOfVertices * row + col;
}

void Dijkstra::setBoard()
{
    source = 0;
    numOfVertices = BOARD_SIZE;
    cout << "Setting board..." << numOfVertices << " source: " << source << "\n";


    for (int i = 0; i < numOfVertices; i++)
    {
        for (int j = 0; j < numOfVertices; j++)
        {
            if (getIndex(i, j) == 7 || getIndex(i, j) == 8 || getIndex(i, j) == 12 || getIndex(i, j) == 17 || getIndex(i, j) == 18)
            {
                adjMatrix[i][j] = 10;
            }
            else
            {
                adjMatrix[i][j] = 1;
            }
        }
    }

    // print board
    printf("\n");
    printf("\n");
    for (int i = 0; i < numOfVertices; i++)
    {
        for (int j = 0; j < numOfVertices; j++)
        {
            if (j == 0)
            {
                printf("\n");
            }
            if (source == getIndex(i, j))
            {
                printf("[X]");
            }
            else
            {
                printf("[%d]", adjMatrix[i][j]);
            }
        }
    }
    printf("\n");
    printf("\n");
}

void Dijkstra::initialize()
{
    for (int i = 0; i < numOfVertices; i++)
    {
        mark[i] = false;
        predecessor[i] = -1;
        distance[i] = INFINITY;
    }
    distance[source] = 0;
}


int Dijkstra::getClosestUnmarkedNode()
{
    int minDistance = INFINITY;
    int closestUnmarkedNode;

    for (int i = 0; i < numOfVertices; i++)
    {
        if ((!mark[i]) && ( minDistance >= distance[i]))
        {
            minDistance = distance[i];
            closestUnmarkedNode = i;
        }
    }
    return closestUnmarkedNode;
}


void Dijkstra::calculateDistance()
{
    int minDistance = INFINITY;
    int closestUnmarkedNode;
    int count = 0;

    while (count < numOfVertices)
    {
        closestUnmarkedNode = getClosestUnmarkedNode();
        mark[closestUnmarkedNode] = true;
        for (int i = 0; i < numOfVertices; i++)
        {
            if ((!mark[i]) && (adjMatrix[closestUnmarkedNode][i] > 0) )
            {
                if (distance[i] > distance[closestUnmarkedNode] + adjMatrix[closestUnmarkedNode][i])
                {
                    distance[i] = distance[closestUnmarkedNode] + adjMatrix[closestUnmarkedNode][i];
                    predecessor[i] = closestUnmarkedNode;
                }
            }
        }
        count++;
    }
}


void Dijkstra::printPath(int node)
{
    if (node == source)
    {
        cout << (char) (node + 97) << "..";
    }
    else if (predecessor[node] == -1)
    {
        cout << "No path from “<<source<<”to " << (char) (node + 97) << endl;
    }
    else
    {
        printPath(predecessor[node]);
        cout << (char) (node + 97) << "..";
    }
}


void Dijkstra::output()
{
    for (int i = 0; i < numOfVertices; i++)
    {
        if (i == source)
        {
            cout << (char) (source + 97) << ".." << source;
        }
        else
        {
            printPath(i);
        }
        cout << "->" << distance[i] << endl;
    }
}


int main()
{
    Dijkstra G;

    G.setBoard();
    G.initialize();
    G.calculateDistance();
    G.output();
    return 0;
}

Answer 1

Once, in void Dijkstra::calculateDistance(), you do

mark[closestUnmarkedNode] = true;

You have the shortest path from source to closestUnmarkedNode.

So you may add just after

if (closestUnmarkedNode == destNode) {
    return;
}

to stop the flood fill. You will have shortest path for all visited nodes including destNode