CODEWITHSUNDEEP
javadata-structuresgraph
David Tunnell
David Tunnell

Reputation: 7542

FInding the shortest path between nodes, and whether a graph is connected

obviously below is a homework problem. I can't understand anything my professor is saying so I don't even need to know where to start looking for the information required to find the answer to this question. If you could give me some leads about where to learn about this stuff as well as how you might approach solving this problem I would be grateful.

In the following graph, find the shortest path between two nodes - your choice, but make the problem interesting.

Is this a connected graph?

enter image description here

Upvotes: 0

Views: 413

Answers (2)

Kit RX
Kit RX

Reputation: 26

It'd be preferable first to know how the graph is represented in memory. If it was up to you, you can use a 2d array as that's the simplest way to represent weighted edges.

The easiest to implement shortest path algorithm is probably Djikstra's which is slightly slower but less complicated than A*. To use Djikastra's you want to first implement a priority queue. In Java there's a PriorityQueue class or you'll have to implement it yourself otherwise. After that, the implementation should be fairly straightforward using pseudo-code that's available on Wikipedia or anywhere else.

Upvotes: 1

75inchpianist
75inchpianist

Reputation: 4102

you should use A star algorithm to find the shortest path between two nodes. http://en.wikipedia.org/wiki/A_star

you can tell if it is connecting using Menger's theorem http://en.wikipedia.org/wiki/Menger%27s_theorem

Upvotes: 1

Related Questions