Dijkstra算法的网格问题的源节点和图

Question

My grid

我正在尝试为上面附加的网格图实现 Dijkstra 算法，以找到从源节点到每个其他节点的最短路径。看了很多教程后，我不明白我应该如何定义我的起始节点和图形。

据我所知，网格不会改变 algorithm/implementation 的工作方式。在每个教程中，我 read/watched 源总是“0”。例如，我读到：Javatpoint article. This is their input: Javapoint graph, Javatpoint Driver class.

所以我想知道输入 'graph' 中行的顺序是否重要？第一行是否总是必须是源节点行？

这是我为我的网格实现驱动程序 class 的尝试：

        int grph[][] = new int[][] {
    //S  A  B  C  D  E  F  G  H  I  J  K
    { 0,-1,-1, 1,-1,-1, 1, 1,-1,-1, 2,-1 }, // S
    {-1, 0, 1,-1,-1, 4,-1,-1,-1,-1,-1,-1 }, // A
    {-1, 1, 0, 4,-1,-1, 9,-1,-1,-1,-1,-1 }, // B
    { 1,-1, 4, 0, 3,-1,-1,-1,-1,-1,-1,-1 }, // C
    {-1,-1,-1, 3, 0,-1,-1, 8,-1,-1,-1,-1 }, // D
    {-1, 4,-1,-1,-1, 0, 2,-1, 2,-1,-1,-1 }, // E
    { 1,-1, 9,-1,-1, 2, 0,-1,-1, 3,-1,-1 }, // F
    { 1,-1,-1,-1, 8,-1,-1, 0,-1,-1,-1, 6 }, // G
    {-1,-1,-1,-1,-1, 2,-1,-1, 0, 1,-1,-1 }, // H
    {-1,-1,-1,-1,-1,-1, 3,-1, 1, 0, 2,-1 }, // I
    { 2,-1,-1,-1,-1,-1,-1,-1,-1, 2, 0, 2 }, // J
    {-1,-1,-1,-1,-1,-1,-1, 6,-1,-1, 2, 0 }, // K
    };

    DijkstraExample obj = new DijkstraExample();
    obj.dijkstra(grph, 0);
    }

我的图表和来源是否正确？

Answer 1

do the order of rows in input 'graph' matter?

没有

Does first row always have to be the row of source node?

没有

例如，您可以重新排列顺序，使“S”排在“F”之后：

int grph[][] = new int[][] {
//A  B  C  D  E  F  S  G  H  I  J  K
{ 0, 1,-1,-1, 4,-1,-1,-1,-1,-1,-1,-1 }, // A
{ 1, 0, 4,-1,-1, 9,-1,-1,-1,-1,-1,-1 }, // B
{-1, 4, 0, 3,-1,-1, 1,-1,-1,-1,-1,-1 }, // C
{-1,-1, 3, 0,-1,-1,-1, 8,-1,-1,-1,-1 }, // D
{ 4,-1,-1,-1, 0, 2,-1,-1, 2,-1,-1,-1 }, // E
{-1, 9,-1,-1, 2, 0, 1,-1,-1, 3,-1,-1 }, // F
{-1,-1, 1,-1,-1, 1, 0, 1,-1,-1, 2,-1 }, // S
{-1,-1,-1, 8,-1,-1, 1, 0,-1,-1,-1, 6 }, // G
{-1,-1,-1,-1, 2,-1,-1,-1, 0, 1,-1,-1 }, // H
{-1,-1,-1,-1,-1, 3,-1,-1, 1, 0, 2,-1 }, // I
{-1,-1,-1,-1,-1,-1, 2,-1,-1, 2, 0, 2 }, // J
{-1,-1,-1,-1,-1,-1,-1, 6,-1,-1, 2, 0 }, // K
};

这涉及同时移动 S-row 和 S-column。

然后您将使用适当的索引调用求解器：

DijkstraExample obj = new DijkstraExample();
obj.dijkstra(grph, 6);

Is my graph and source correct?

矩阵和主要代码（2 条语句）是正确的，但很大程度上取决于您的 class 所做的事情。

Dijkstra算法的网格问题的源节点和图

Dijkstra Algorithm's source node and graph for grid problem

java

algorithm

dijkstra