quda

quda

Hi,
I am quite new to Elixir… about one month experience.
I’m trying to implement a program for shortest path calculation between two points using Breadth-first search (BFS) algorithm on a directed graph, using recursion.
The code I wrote is this:

defmodule BFS do
  def neibors(node, edges) do
    Enum.filter(edges, fn x -> x.from == node end)
    |> Enum.map(& &1.to)
  end

  def bfs(start, target, graph) do
    que = neibors(start, graph)
    visited = [start]
    Enum.reverse(search(que, {target, graph}, visited, [start]))
  end

  defp search([node | rest], data, visited, prev) do
    {target, graph} = data
    if Enum.member?(visited, node) == false do
      if node == target do
         [target|prev]
      else
        search(neibors(node, graph) ++ rest, data, [node | visited], [node | prev])
      end
    end
  end
end

The test graph picture I cannot upload (new users cannot upload pictures) :face_with_raised_eyebrow:
But this is the test data model I use:

graph = [
  %{from: 'A', to: 'B'},
  %{from: 'A', to: 'C'},
  %{from: 'B', to: 'G'},
  %{from: 'C', to: 'F'},
  %{from: 'C', to: 'D'},
  %{from: 'D', to: 'E'},
  %{from: 'E', to: 'H'},
  %{from: 'F', to: 'D'},
  %{from: 'F', to: 'G'},
  %{from: 'H', to: 'G'}
]

I want to get the shortest path from node A to node H. This is obviously A->C->D->E->H

I cannot manage to collect the path’s nodes, instead it collects all traversed nodes:

 BFS.bfs('A', 'H', graph) 
['A', 'B', 'G', 'C', 'F', 'D', 'E', 'H']

Obviously, something is wrong in my algorithm implementation, I need a way to collect only the nodes of the shortest path not all of them. How ?

Thanks in advance for your help!

Showing Posts 1 to 4

dimitarvp

dimitarvp

Upload it somewhere public and put a link here?

hernytan

hernytan

The code you have written is not a BFS, but actually a DFS. This is because after you visit a node, you push its neighbors into the front of the queue, when you should push it onto the back of the queue. Remember: going to the front is cutting the queue!

More importantly, your code also doesn’t handle the case when you do revisit a node. Say you go from A → B → A. Then your search function just returns nothing.

Also, you should add a case to handle if the target node is missing. Maybe return an :error

A suggestion, you can also make the visited data structure a MapSet, that way you can use the in-built data functions to test if a node has been visited:

quda

quda OP

here it is

quda

quda OP

Thanks for your suggestions, @hernytan.

I inversed by putting queue in front on neighbors

  search(rest ++ neibors(node, graph), data, [node | visited], [node | prev])

The result is even worse:

iex(4)> BFS.bfs('A','H',edges)
nil

More importantly, your code also doesn’t handle the case when you do revisit a node. Say you go from A → B → A. Then your search function just returns nothing.

I don’t get this… What should return in this case?

About the third hint, that with MapSet, I’m afraid I don’t know how to do this.

Thanks anyway.

— All posts loaded —

Where Next? Top

Trending in Questions Top

katta
I having some trouble figuring out if I have set myself too strict of standards for my production server. Currently I can handle 75% of r...
New
achenet
Hello, I’m trying to build a basic Phoenix web-app, and I’d like to use Tailwind. However, when I launch mix phx.server, I get an error...
New
kpanic
Hi everyone, I am toying with the idea of building a “match maker” for giving personal help to people that wants to start coding. I sta...
New
Cxx-mlr
I’m working on a small exercise involving update_in/3, and I came up with this solution: data = %{ name: "Periodic Table", category:...
New
ChrisAmelia
I’ve got trouble wrapping my head around the order in which functions are called in this snippet (from Phoenix’s authentication): toke...
New
dillonoconnor
Is there any way to avoid the Hologram compiler running when using iex? It seems like the front-end code could potentially be disregarded...
New
thiagogsr
** (ArgumentError) expected :max_attempts to be a positive integer, got: {:@, [line: 10, column: 19], [{:max_attempts, [line: 10, column:...
New

Other Trending Topics Top

GenericJam
Edit: 2026 May 15 - This post is archived. Mob is alive!! Main docs: mob v0.7.11 — Documentation A bit of explanation for the slightly c...
New
mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
garrison
Hobbes is a low-level distributed database for the Elixir programming language. Hobbes provides a simple, safe, and scalable storage lay...
New
budgie
A little off-topic, but I feel like people here have a good head on their shoulders. I used to be quite good at making software. Was luc...
New
KristerV
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
mcass19
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews