prim, a Python code which implements Prim's algorithm to compute a minimal spanning tree of a weighted graph.
For a graph of VN nodes, the algorithm expects to work with a VNxVN weight matrix W, with the properties that:
W[i,i] = 0
W[i,j] = W[j,i] for all i, j
0 < W[i,j] for i and j distinct
W[i,j] = np.inf if there is no link from node i to node j
The algorithm returns an NV-1x2 LINKS array, containing pairs (I,J) representing the links in the spanning tree.
The information on this web page is distributed under the MIT license.
prim 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.
toms097, a Python code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.