c++ - 如何应用泛洪算法为加权二维矩阵找到指定源位置和目标位置之间的最佳路径

Question

我一直在尝试实现一个类，该类使用泛洪算法为指定源索引和目标索引之间的最佳路径生成索引列表。

如:

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

例如，给定一个 5x5 的二​​维矩阵，找到 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]) && ( 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

一次，在 void Dijkstra::calculateDistance() 中，您可以

mark[closestUnmarkedNode] = true;

您有从 source 到 closestUnmarkedNode 的最短路径。

所以你可以在之后添加

if (closestUnmarkedNode == destNode) {
    return;
}

阻止洪水填满。您将拥有所有访问节点的最短路径，包括 destNode