Hi all!
I know this isn't a specific Java question, but I couldn't find a "General" subforum and we use Java in the class I'm taking so bare with me.
Moderators are more than welcome to move the thread if there's a better match for it somewhere else. :)
I have two big questions that I need to answer for a school assignment, and I need some help.
The questions are:
A)
Which of the following (see below) algorithms work with multigraphs (that is, graphs with one or more edges between two vertices/nodes)?
What changes can you make for the ones that don't work to make them work?
B)
Which of the following algorithms work with negative cost/weight edges?
What changes can you make for the ones that don't work to make them work?
Algorithms:
Prim's
Kruskal's
Dijkstra's
Depth first search
Breadth first search
Topological sort(order)
My answers are:
A)
They all work, but that for topological sort the graph must be acyclic.
B)
Prim and Kruskal work w/o modification. Dijkstra does not work, and if you make a change to it to make it work it will turn into Prim.
Breadth first search only works on unweighted graphs, hence there's nothing you can do to it to make it work on weighted.
Topological sort does not work since it only works on acyclic graphs, and with negative weights you risk ending up in an infinite loop.
Depth first search works w/o modification.
So, am I totally wrong on everything or am I in the ball-park?
Any hints and/or help is greatly appreciated!
Thanks,
SL