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) ![]()
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!
Trending in Questions
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
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
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
I’m working on a small exercise involving update_in/3, and I came up with this solution:
data = %{
name: "Periodic Table",
category:...
New
I’ve got trouble wrapping my head around the order in which functions are called in this snippet (from Phoenix’s authentication):
toke...
New
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
** (ArgumentError) expected :max_attempts to be a positive integer, got: {:@, [line: 10, column: 19], [{:max_attempts, [line: 10, column:...
New
Other Trending Topics
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
I am happy to introduce the very α version of the new programming language compiled to BEAM.
Welcome Cure.
It has literally three kille...
New
Hobbes is a low-level distributed database for the Elixir programming language.
Hobbes provides a simple, safe, and scalable storage lay...
New
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
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
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ai
- #ecto-query
- #elixirconf-us
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #metaprogramming
- #hex










Showing Posts 1 to 4- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
dimitarvp
Upload it somewhere public and put a link here?
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
:errorA 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
here it is
quda
Thanks for your suggestions, @hernytan.
I inversed by putting queue in front on neighbors
The result is even worse:
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.