0

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

3
  • I would read my notes. Mar 4, 2013 at 19:50
  • 1
    @SotiriosDelimanolis To be honest with you, I rarely find my lecture notes useful. Most of the time I use online tutorials or youtube videos to expands on the topics from my notes, as most of the time they're just a summary of what the lecturer has said during the lecture.
    – Kakalokia
    Mar 4, 2013 at 19:51
  • 1
    Also Google for graph shortest path and read some of the search results. Mar 4, 2013 at 19:52

2 Answers 2

1

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.

1

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.