Different formats for shortest path algorithm

The two references use two different, but common, representations of a graph:

1. Adjacency list

   The referenced code looks like this:

   class Node {
       private Map<Node, Integer> adjacentNodes = new HashMap<>();
       // ...
   }
   

   ... and then calling the Node constructor and methods to actually create the nodes and edges of the actual graph.

2. Adjacency matrix

   The referenced code looks like this:

   int graph[][] = new int[][] {
       {0, 4, 0, 0, 7},
       {4, 0, 1, 2, 0},
       {0, 1, 0, 6, 0},
       {0, 2, 6, 0, 0},
       {7, 0, 0, 0, 0}
   };
   

The two data structures are documented at Wikipedia:

• Adjacency matrix:

  For a simple graph with vertex set 𝑈 = {𝑢₁, …, 𝑢_𝑛}, the adjacency matrix is a square 𝑛 × 𝑛 matrix 𝐴 such that its element 𝐴_𝑖𝑗 is one when there is an edge from vertex 𝑢_𝑖 to vertex 𝑢_𝑗, and zero when there is no edge.

  [...]

  It is also possible to store edge weights directly in the elements of an adjacency matrix.

• Adjacency list:

  An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges.

  The article goes on with details about how this can be implemented, as there are quite a few ways to do it.

These two structures have their own advantages and disadvantages. Both Wikipedia articles mention several of these trade-offs, including space and time efficiency concerns.

I'd like to add that in this particular matrix representation there is no way to encode an edge that has a weight of zero, as 0 is reserved for indicating there is no edge.

For the purpose of Dijkstra's algorithm, it will in general be more efficient to use the adjacency list approach. A boundary case is when the graph has edges between (almost) any pair of vertices -- in that case an adjacency matrix might be more useful.