Struct graph_algorithms::list_of_algorithms::bellmanford::bellmanford::Graph

pub struct Graph {
    edges: Vec<(usize, usize, i32)>,
    vertices: usize,
}

Fields

edges: Vec<(usize, usize, i32)>

representation using edge list

vertices: usize

total no of vertices

Implementations

impl Graph

pub fn new(vertices: usize) -> Self

pub fn add_edge(&mut self, u: usize, v: usize, w: i32)

Adding edges to the graph

pub fn bellman_ford(&self, src: usize) -> Vec<i32>

Bellman-Ford algorithm Bellman ford algorithm is used to find the shortest node from one node to all other nodes in a weighted graph

Arguments

• vector(s,d,w) - A vector representing the source, destination and weight
• start - The index of the vertex to start the Bellman Ford algorithm from.

Returns

• vector(s,d,w) -Returns the vector of the shortest distance from source to destination after Bellman Ford is run.

Example

 let  = vec![
 vec![0,1,-1], // Node 0 has edges to node 1 and weight -1
 vec![0,2,4],  // Node 0 has edges to node 2 and weight 4
 vec![1,2,3],  // Node 0 has edges to node 2 and weight 4
 vec![3,2,5],  // Node 0 has edges to node 2 and weight 4
 vec![3,1,1],  // Node 0 has edges to node 2 and weight 4
 vec![1,3,2],  // Node 0 has edges to node 2 and weight 4
 vec![1,4,2],  // Node 0 has edges to node 2 and weight 4
 vec![4,3,-3], // Node 0 has edges to node 2 and weight 4
 ];
 let start_vertex = 0;
  
 let visited = bfs(&adj_list, start_vertex);

 assert_eq!(visited, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);