Dijkstra Algorithm's source node and graph for grid problem-CodePudding

My grid

Im trying to implement Dijkstra algorithm for grid-like graph attached above to find shortest path from source node to every other node. Having watched many tutorials I fail to understand how I am supposed to define my starting node and graph.

As far as I understand grid doesnt change how algorithm/implementation works. In every tutorial I read/watched source is always "0". For example I read this: Javatpoint article. This is their input: Javapoint graph, Javatpoint Driver class.

So I wonder do the order of rows in input 'graph' matter? Does first row always have to be the row of source node?

This is my attempt at implementing driver class for my grid:

        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);
    }

Is my graph and source correct?

CodePudding user response：

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

No.

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

No.

For instance, you could reorganise the order, so that "S" is ordered after "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
};

This involves moving both the S-row and S-column.

You would then call the solver with the appropriate index:

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

Is my graph and source correct?

The matrix and the main code (2 statements) are correct, but much depends on what your class does.