CODEWITHSUNDEEP
javaalgorithmshortest-pathadjacency-list
sqram
sqram

Reputation: 7201

Shortest path in an adjacency list in non-weighted graph

First, I would like to make sure I got the structure correct. As far as I know, an adjacency list representing a graph looks like this:

an adjacent list

AdjList is an ArrayList, where each element is an object. Each object contains an ArrayList inside to represent vertices connected. So for example, in the image above, Vertext 1 (first index in the AdjList) is connected to the vertex at index 2, 4, and 5 of the AdjList. Is this representation of an adjacency list correct? (ps: I know indices start at 0, i put 1 here for simplicity/ease).

If it is correct, which algorithm should I use to find the shortest path between two vertices?

Upvotes: 1

Views: 6580

Answers (4)

Carlos Julio
Carlos Julio

Reputation: 410

Previous answers mention disjktra and floyd algorithms to resolve the problem and are valid solutions, but where the graph is unweighted, the best solution is use a BFS technique, simpler and optimal.

BFS has a algorithm complexity of O(n), while disjktra O(n * log(n)) and Floyd O(n^2)

Upvotes: 1

piyush_raman
piyush_raman

Reputation: 318

You can use Dijkstra's and Floyd Warshall. For unweighed graph assume weight of each edge to be 1 and apply the algorithm.

Upvotes: 1

Tudor
Tudor

Reputation: 62439

There is no algorithm to give you just the shortest path between two vertices. You can use either:

  1. Dijkstra's algorithm to find the shortest path between one vertex and all the others (and then choose the one you need).
  2. Roy-Floyd algorithm to find the shortest path between all possible pairs of vertices.

The links also include pseudocode.

Upvotes: 4

Arnon Rotem-Gal-Oz
Arnon Rotem-Gal-Oz

Reputation: 25909

Here's an example for Dijkstra's shortest path algorithm in java along with explanations

Upvotes: 2

Related Questions