kruskal, a Python code which implements Kruskal's algorithm to compute a minimal spanning tree of a weighted graph.
For a graph of VN nodes and EN edges, the algorithm expects to work with a ENx3 EDGES array, with each row containing values W, I, J, representing the weight and two end nodes of an edge.
The algorithm returns an (VN-1)x3 LINKS array, listing triples (W,I,J) representing the weight and links of the edges forming the spanning tree.
The information on this web page is distributed under the MIT license.
kruskal is available in a Python version
bellman_ford, a Python code which implements the Bellman-Ford algorithm for finding the shortest distance from a given node to all other nodes in a directed graph whose edges have been assigned real-valued lengths.
dijkstra, a Python code which implements the Dijkstra algorithm for finding the minimum distance from a given node of a weighted graph to all the other nodes.
floyd, a Python code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
graph_adj, a Python code which carries out operations on abstract graphs, with undirected edges, represented by an adjacency matrix. Operations included breadth-first search, the computation of a minimum spanning tree, an Euler or Hamilton circuit, blocks, chromatic polynomial, or transitive closure.
graph_dist, a Python code which carries out operations on abstract graphs, defined by undirected edges with an associated distance matrix, including the computation of the minimal spanning tree.
prim, a Python code which implements Prim's algorithm to compute a minimal spanning tree of a weighted graph.
toms097, a Python code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.