0

I have to do the following task: "You have a graph G(V,E) and to of its vertices x and y . Write a program that finds the shortest way between 2 vertices , by the number of vertices.

I don't understand if it's up to me to decide whether this graph is directed or not or whether I should have a edge class or what kind graph implementation to make. This is the first exercise in the chapter "Trees and graphs" of my book(Introduction to programming with java) and I don't know where to begin. How would you do it and why ?

Radoslav Monov
  • 9
  • 2
  • Maybe this [link](http://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path-java) gives you some ideas for the search. – Stefan Freitag May 25 '15 at 13:26
  • Doesn't sound like it's directed. Have a read of https://en.wikipedia.org/wiki/Shortest_path_problem, perhaps. – Armand May 25 '15 at 13:27
  • @Radoslav Monov - Is the help enough or I should elaborate my post further? Either use adjacency matrix or adjacency list to represent the graph in your program. – Petar Minchev May 25 '15 at 15:46

2 Answers2

0

You are looking for Dijkstra's algorithm. It will give you the shortest path on any graph between two points, to use that algorithm you will need to know how to use graphs themselves and priority queues. Wikipedia has a very good article on the algorithm.

cujo
  • 368
  • 3
  • 16
  • 1
    By number of vertices he is looking for the BFS algorithm, not Dijkstra. – Petar Minchev May 25 '15 at 13:34
  • Dijkstra's will do that as well if its treated as an unweighted graph. – cujo May 25 '15 at 13:35
  • 1
    BFS is not guaranteed to find the shortest path, Dijkstra's is. Hence why it is a search and not a path finding tool. – cujo May 25 '15 at 13:36
  • 1
    Read carefully - `Write a program that finds the shortest way between 2 vertices , by the number of vertices.` He wants the shortest path by number of vertices. The graph is not weighted. – Petar Minchev May 25 '15 at 13:37
  • And for this task Dijkstra is not as efficient as BFS. – Petar Minchev May 25 '15 at 13:37
  • My problem isn't the algorithm of finding the shortest way . I wish to come up with that on my own (the hint for the exercise tells me to use BFS) but after I implemented what I thought would do the job i found out it couldn't . So I guess I should correct my question - how should I implement the graph ? – Radoslav Monov May 25 '15 at 13:39
  • BFS does not generate a path though, it generates simply a list of accessible vertices. But I'm theory, to get just the distance and not the path (which is what he is looking for) then you could use BFS – cujo May 25 '15 at 13:40
  • You could restore the path easily using BFS. – Petar Minchev May 25 '15 at 13:40
  • @RadoslavMonov - The input should be N, M - N is number of vertices, M - number of edges. Then a list of size M with the edges. Make it not directed. – Petar Minchev May 25 '15 at 13:41
  • If it's simply based on number of edges, you want an undirected unweighted graph. – cujo May 25 '15 at 13:43
  • @RadoslavMonov - For the graph represenation start with an adjacency matrix. It is the simplest one. Then you can try with adjacency list. – Petar Minchev May 25 '15 at 13:57
  • From personal experience, adjacency list has been my favorite to use. – cujo May 25 '15 at 14:04
  • Yes, and adjacency list is more efficient than the adjacency matrix when the graph is sparse. – Petar Minchev May 25 '15 at 14:05
0

Since it is not told that it is directed in the question, then assume it is undirected. Also they want you to find the shortest path by number of vertices, so it is also unweighted. Assume it is undirected and unweighted.

For example - N - number of vertices, M - number of edges

4 5
1 2
2 3
3 4
1 3
2 4

For the graph representation either use an adjacency matrix (the simplest one) or an adjacency list. The adjacency matrix is a two-dimensional array G where G[a][b] is true when there is an edge between a and b and false otherwise.

Petar Minchev
  • 46,889
  • 11
  • 103
  • 119