0

Graph

Adjacency Matrix

First off, I apologize for my bad paint drawing of the graph. The weights are obviously not scaled. I am having a hard time coming up with the algorithms to solve a few problems.

First, I want to find all paths that take 3 "stops" or less from C to C (just an example... can be any two vertexes). After researching, I found that BFS might be what I'm looking for to solve this problem. Am I correct in this assumption?

There are two paths that have 3 stops or less:

C -> D -> C

C -> E -> B -> C

I also want to find the shortest path from A to C (just an example.. can be any two vertexes). After doing a little bit of research, I came to the conclusion that I should use Dijkstra's algorithm. Am I correct in this assumption? If so, I saw that there are various implementations. Does it matter if I use binary heap, fibonacci heap, or queue?

Thank you and please let me know if you need any more information!

ShadyBears
  • 3,955
  • 13
  • 44
  • 66

1 Answers1

0

First, I want to find all paths that take 3 "stops" or less from C to C (just an example... can be any two vertexes). After researching, I found that BFS might be what I'm looking for to solve this problem. Am I correct in this assumption?

Yes, you are. The property of BFS is that processes nodes in level-order, therefore you first process all nodes that are neighbors of the source node, then the nodes that are neighbors of neighbors of the source node etc.

I also want to find the shortest path from A to C (just an example.. can be any two vertexes). After doing a little bit of research, I came to the conclusion that I should use Dijkstra's algorithm. Am I correct in this assumption? If so, I saw that there are various implementations. Does it matter if I use binary heap, fibonacci heap, or queue?

Again, yes, Dijkstra's algorithm is a classic solution for such problems. There are other algorithms better suited for some special situations (e.g. Bellman-Ford if you have negative weights in your graph), but in most cases (yours as well), go with Dijkstra. Regarding the implementation, theoretically the best implementation is based on a min-priority queue implemented by a Fibonacci heap. The running time of this implementation is O(|E|+|V|/log|V|) (where |V| is the number of vertices and |E| is the number of edges). However, in practice, binary heaps often outperform Fibonacci heaps, see this interesting thread for more information.

Community
  • 1
  • 1
Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66
  • is this a proper way of finding all paths "from C to C"- start DFS from C and output path everytime we find "back edge" to C ? – mangusta Sep 21 '15 at 09:09
  • @mangusta Not sure about it. DFS is, pretty much like BFS, an algorithm for graph traversal, not for finding *all* paths. However, if you introduce the constraint on the path length, then you can avoid marking nodes as visited and thus find all paths of the certain length. Without that constraint and without marking nodes as visited, you'll get stuck in the infinite loops. – Miljen Mikic Sep 21 '15 at 09:58
  • @mangusta I have thought a little bit more about it. It is possible with DFS, but in order to get all paths, you will have to remove node from the visited list after the recursive call. – Miljen Mikic Sep 21 '15 at 10:22