Блог

Я пытался реализовать класс, который использует алгоритм затопления для генерации списка индексов для оптимального пути между указанным исходным и целевым индексом.

Например:

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

Например, учитывая 2d-матрицу 5×5, найдите оптимальный путь между между X и 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]
  

Ожидаемый результат:

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

Где приведенные выше значения индекса сопоставляются с индексами строк и столбцов в матрице:

 index = numOfVertices * rowNumber   rowNumber
  

Я нашел несколько разных вариантов, но пока нет реализации, которая выполняет вышеуказанное.

Этот алгоритм, который я в настоящее время пытаюсь распространить на это, я нашел здесь:

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

Хотя я не вижу, как здесь можно указать узел назначения, поэтому я изо всех сил пытаюсь понять, как я могу это расширить.

Моя версия приведена ниже, компилируется и работает нормально, однако вы можете указать индекс источника только в функции setBoard() .

Код:

 #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]) amp;amp; ( 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]) amp;amp; (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;
}
  

После void Dijkstra::calculateDistance() ввода вы делаете

 mark[closestUnmarkedNode] = true;
  

У вас есть кратчайший путь от source до closestUnmarkedNode .

Таким образом, вы можете добавить сразу после

 if (closestUnmarkedNode == destNode) {
    return;
}
  

чтобы остановить заливку.
У вас будет кратчайший путь для всех посещенных узлов, включая destNode