Graph Algorithms

A collection of graph algorithms implemented in Rust. This repository aims to provide efficient and easy-to-understand implementations of various graph algorithms for educational purposes and practical use.

Contributions are welcome to expand the set of algorithms and improve existing implementations.

Reference implementation

Algorithms

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph. It uses a priority queue to efficiently select the next node with the smallest distance.

Bellman-Ford Algorithm

The Bellman-Ford algorithm computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It can handle graphs with negative weight edges.

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with negative weights but no negative weight cycles.

A* Algorithm (TODO)

A* is a pathfinding and graph traversal algorithm that is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.

Breadth-First Search (BFS) (TODO)

BFS explores the graph level by level, starting from a given node. It is used for finding the shortest path in an unweighted graph.

Depth-First Search (DFS) (TODO)

DFS explores as far as possible along each branch before backtracking. It is used for pathfinding and topological sorting.

Safety

This crate uses #![forbid(unsafe_code)] to ensure everything is implemented in 100% safe Rust.

Usage

The examples directory contains example implementations of various graph algorithms:

use graph_algorithms::{DijkstraAlgorithm, GraphAlgorithm};

Features

This crate provides optional features for different algorithms.

By default, all features are enabled. You can customize the features when adding the dependency in your Cargo.toml:

[dependencies]
graph-algorithms-rs = { version = "x.x.x", default-features = false, features = ["dijkstra"] }

For a detailed list of available algorithms, refer to the Algorithms section.

Contributing

Build the application:

cargo build

Test the application:

cargo test

Run clippy:

cargo clippy --all-targets --all-features --no-deps -- -D warnings

Run lint:

cargo fmt

Generate documentation in HTML format:

cargo doc --open