Typically, I know Bellman-Ford finds the shortest path between the source vertex and every other vertex. My question is, if trying to get the full path length i.e starting with a vertex and ending with the same vertext e.g starting with USD in a trade path and making sure to end the path with USD (same currency in and out), do I need to perform the relaxation again?

For instance, I’m trying to get all possible paths from the entire graph using this method; going from a source to every other vertex – then from each of those other vertex back to the source. Does this last part need a recomputation of the relaxation step? If it does, is it supposed to produce the same predecessors mapping but with different distances?

Plus if my reasoning about how to compute all possible paths is wrong, can I get some guidance?

fn bellman_ford(
    graph: &Graph<Address, f64>,
    start: Address,
    end: Option<Address>,
) -> Option<Vec<Vec<(Address, Address, f64)>>> {
    let mut trading_sequence: Vec<(Option<Address>, Option<Address>, f64)> = vec![];
    let mut all_trading_sequences: Vec<Vec<(Address, Address, f64)>> = vec![];

    let num_vertices = graph.len();
    let vertice_keys: Vec<Address> = graph.keys().cloned().collect();
    
    let start_vertex = Some(start);
    trading_sequence = vec![];
    
    // Returns a path 
    if start_vertex != end && end != None {
        trading_sequence = get_path(Some(start), end, &graph, num_vertices);
        
        // path discovered
        if trading_sequence.len() > 0 {
            // do some checks to make sure the path is has no empty input along it
        }

        return Some(vec![]); // return after formatting and checking
    } else { // at this point start == end, or end is None which implies the former holds
        // here i want to get the best paths from source to every node, then from every node 
        // back to source. then concatenate the results
        for vertex_key in vertice_keys {
            if vertex_key == start { continue; }
            trading_sequence = get_path(Some(start), Some(vertex_key), &graph, num_vertices);

            // there's no path, continue 
            if trading_sequence.len() == 0 { continue; }
            // get return back to source
            let mut ret = get_path(Some(vertex_key), Some(start), &graph, num_vertices);
            // there's no path, continue 
            if ret.len() == 0 { 
                trading_sequence = vec![]; // clear path
                continue; 
            }

            trading_sequence.append(&mut ret); 

            println!("Full sequence -> {:?}", trading_sequence);

            //all_trading_sequences.push() after processing and checks
            trading_sequence = vec![];
        }
    }

    Some(vec![])
}

fn get_path(
    start_vertex: Option<Address>,
    end_vertex: Option<Address>,
    graph: &Graph<Address, f64>,
    num_vertices: usize,
) -> Vec<(Option<Address>, Option<Address>, f64)> {
    let mut trading_sequence: Vec<(Option<Address>, Option<Address>, f64)> = vec![];
    let mut count = 0;
    let mut previous = end_vertex;
    
    let parent = relaxation(graph, start_vertex.unwrap());

    loop {
        count += 1;
            
        // constructing a path from a node to itself, typically results in a weight of 0 
        // as no edges need to be traversed to reach itself. n - 1 
        if previous == start_vertex { break; }
        if previous == None { break; }

        if let Some(tk) = parent[&previous.unwrap()] {
            let u_vertex = parent[&previous.unwrap()];
            let mut temp: (Option<Address>, Option<Address>, f64) = (None, None, 0.0);
            temp.0 = Some(tk);
            temp.1 = previous;

            match (temp.0, temp.1) {
                (Some(u), Some(v)) => {
                    let ans = match graph.get(&u) {
                        Some(inner_graph) => match inner_graph.get(&v) {
                            Some(weight) => *weight,
                            None => 0.0, // no corresponding entry
                        },
                         _ => 0.0, // there's always gonna be something here, won't be reached
                    };
                    temp.2 = (-ans).exp();
                    ans
                },
                _ => 0.0,
            };
            trading_sequence.push(temp);

            previous = Some(tk);
        } else {
            previous = None;
        }
        if count == num_vertices - 1 { break; }
    }
    trading_sequence.reverse();

    trading_sequence
}

// returns parents/predeccessors for constructing path
fn relaxation(graph: &Graph<Address, f64>, start: Address) -> HashMap<Address, Option<Address>> {
    let mut distance: HashMap<Address, f64> = HashMap::new();
    let mut parent: HashMap<Address, Option<Address>> = HashMap::new();

    let num_vertices = graph.len();
    let vertice_keys: Vec<Address> = graph.keys().cloned().collect();
    
    // Initialize single source
    // for each vertex v is an element of G.V
    for vertice_key in &vertice_keys {
        // distance set to infinity as an upper bound
        distance.insert(*vertice_key, f64::INFINITY);
        parent.insert(*vertice_key, None);
    }
    //distance[&start] = 0.0;
    distance.entry(start).and_modify(|d| *d = 0.0 );

    let mut negative_cycle_source: Option<Address> = None;

    // relax edges num_vertices - 1 times
    for i in 0..num_vertices - 1 {
        for (u, edges) in graph {
            for (v, edge_weight) in edges {
                if distance[u] != f64::INFINITY && distance[v] > distance[u] + edge_weight {
                    let dist_u = distance[u];
                    //let dist_u = *distance.get(u).unwrap();
                    distance.entry(*v)
                        .and_modify(
                            |weight| *weight = dist_u + edge_weight
                        );
                    //distance[v] = distance[u] + edge_weight;
                    //parent[v] = Some(*u);
                    parent.entry(*v)
                        .and_modify(
                            |p| *p = Some(*u)
                        );
                }
            }
        }
    }

    parent
}

Here, the code is very rough I know – I will refactor as soon as I’m sure I’m doing the right thing; I’m just debugging and doing excess computations which will be resolved as soon as I get it working well.

On each iteration of source -> other vertex and other vertex -> source, this produces different distance value mappings but the same predecessors/parents mapping. Is this correct? Plus building paths this way gives inconsistent flows too.

[(a, b, e1), (b, c, e2), ...] -> means going from a to b using edge e1, then b to c using edge e2,...

=====================================================
Some(Currency 1) - Some(Currency 2)


Full sequence -> [(Some(Currency 1), Some(Currency 2), 5000.000000000004), (Some(Currency 1), Some(Currency 4), 4500.000000000001), (Some(Currency 4), Some(Currency 3), 1.08), (Some(Currency 3), Some(Currency 1), 0.002099999999999999)]
=====================================================

=====================================================
Some(Currency 1) - Some(Currency 3)

Full sequence -> [(Some(Currency 1), Some(Currency 4), 4500.000000000001), (Some(Currency 4), Some(Currency 3), 1.08), (Some(Currency 3), Some(Currency 1), 0.002099999999999999)]
=====================================================

=====================================================
Some(Currency 1) - Some(Currency 4)

Full sequence -> [(Some(Currency 1), Some(Currency 4), 4500.000000000001), (Some(Currency 4), Some(Currency 3), 1.08), (Some(Currency 3), Some(Currency 1), 0.002099999999999999)]
=====================================================