Prims and Bellman-Ford Algorithms in Directed Graphs

Please suggest resources to learn how to find a minimal spanning tree in a directed graph using Pr开发者_Python百科im's algorithm, as well as Bellman-Ford algorithm to calculate the shortest path in a directed graph.

Finding an MST from a directed graph is a different problem, for which you cannot simply adapt Prim's. You should instead use Edmond's algorithm.

Bellman Ford already works on directed graphs. No need to alter anything.

The links provided should get you started. Google for additional resources if necessary.

If you'd like some actual code for the algorithms, I recently coded both of these algorithms up.

• Prim's algorithm
• Bellman-Ford algorithm

The comments at the top of these files contains an analysis of the two algorithms both from a correctness and runtime perspective, and I hope they can shed some light on how they work.

The alsuwaiyel textbook on Google Books is very good and has most of the book available.