path

func BellmanFord ¶ added in v0.4.1

func BellmanFord[T comparable](g gograph.Graph[T], start T) (map[T]float64, error)

BellmanFord finds the shortest path from a source vertex to all other vertices in a weighted graph, even in the presence of negative weight edges, as long as there are no negative weight cycle.

Steps:

	1.Initialization: Start by setting the distance of the source vertex to itself
    as 0, and the distance of all other vertices to infinity.

	2. Relaxation: Iterate through all edges in the graph |V| - 1 times, where |V|
	is the number of vertices. In each iteration, attempt to improve the shortest
	path estimates for all vertices. This is done by relaxing each edge: if the distance
	to the destination vertex through the current edge is shorter than the current
	estimate, update the estimate with the shorter distance.

	3.Detection of Negative Cycles: After the |V| - 1 iterations, perform an additional
	iteration. If during this iteration, any of the distances are further reduced, it
	indicates the presence of a negative weight cycle in the graph. This is because if a
	vertex's distance can still be improved after |V| - 1 iterations, it means there's a
	negative weight cycle that can be traversed indefinitely to reduce the distance further.

	4.Output: If there is no negative weight cycle, the algorithm outputs the shortest path
	distances from the source vertex to all other vertices. If there is a negative weight
	cycle, the algorithm typically returns an indication of this fact.

The time complexity of the Bellman-Ford algorithm is O(V*E), where V is the number of vertices and E is the number of edges.

func Dijkstra ¶

func Dijkstra[T comparable](g gograph.Graph[T], start T) map[T]float64

Dijkstra is a standard implementation of Dijkstra's Algorithm that uses a min heap as a priority queue to find the shortest path between start vertex and all other vertices in the specified graph.

The time complexity of the standard Dijkstra's algorithm with a min heap is O((E+V)logV).

It returns the shortest distances from the starting vertex to all other vertices in the graph.

func DijkstraSimple ¶

func DijkstraSimple[T comparable](g gograph.Graph[T], start T) map[T]float64

DijkstraSimple is a simple implementation of Dijkstra's algorithm. It's using a simple slice to keep track of unvisited vertices, and selected the vertex with the smallest tentative distance using linear search.

The time complexity of the simple Dijkstra's algorithm implementation is O(V^2).

It returns the shortest distances from the starting vertex to all other vertices in the graph.

func FloydWarshall ¶ added in v0.4.1

func FloydWarshall[T comparable](g gograph.Graph[T]) (map[T]map[T]float64, error)

FloydWarshall finds the shortest paths between all pairs of vertices in a weighted graph, even in the presence of negative weight edges (as long as there are no negative weight cycles). It was proposed by Robert Floyd and Stephen Warshall.

Steps:

1. Initialization: Create a distance matrix D[][] where D[i][j] represents the shortest distance between vertex i and vertex j. Initialize this matrix with the weights of the edges between vertices if there is an edge, otherwise set the value to infinity. Also, set the diagonal elements D[i][i] to 0.

2. Shortest Path Calculation: Iterate through all vertices as intermediate vertices. For each pair of vertices (i, j), check if going through the current intermediate vertex k leads to a shorter path than the current known distance from i to j. If so, update the distance matrix D[i][j] to the new shorter distance D[i][k] + D[k][j].

3. Detection of Negative Cycles: After the iterations, if any diagonal element D[i][i] of the distance matrix is negative, it indicates the presence of a negative weight cycle in the graph.

4. Output: The resulting distance matrix D[][] will contain the shortest path distances between all pairs of vertices. If there is a negative weight cycle, it might not produce the correct shortest paths, but it can still detect the presence of such cycles.

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph. Despite its cubic time complexity, it is often preferred over other algorithms like Bellman-Ford for dense graphs or when the graph has negative weight edges and no negative weight cycles, as it calculates shortest paths between all pairs of vertices in one go.

func TransitiveReduction ¶ added in v0.6.0

func TransitiveReduction[T comparable](g gograph.Graph[T]) (gograph.Graph[T], error)

TransitiveReduction computes the transitive reduction of a directed graph. The transitive reduction of a directed graph G is a graph G' with the same vertices such that there is a path from vertex u to vertex v in G' if and only if there is a path from u to v in G, and G' has as few edges as possible.

This implementation uses a depth-first search approach inspired by NetworkX library to efficiently compute the transitive reduction by identifying and removing edges that have alternate paths.

For directed acyclic graphs (DAGs), the transitive reduction can be computed efficiently without needing to build the full transitive closure matrix.

It returns an error if the graph is not directed or if the graph contains cycles.