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
Hello!
Suppose you are building workflow (order / task / payment) processing system with the following requirements:
Each workflow con...
New
I’m in search of an Elixir library that offers PDF generation capabilities similar to Ruby’s Prawn. While there have been discussions abo...
New
I’m looking to build a personal workflow to quickly deploy web applications written in elixir/phoenix, for local consumption (ie not on t...
New
Before I dive in myself, did anyone successfully sprinkle Hologram into their existing LiveView app?
Looking for hints regarding:
Addi...
New
Kia ora,
We have been using elixir-google-api to connect to Google Drive. However, with the updates to Tesla due to CVEs this is now bro...
New
Hi all, I wanted to ask how the community is dealing with post-release steps.
Today we have Ecto migrations, which make sure that the db...
New
Hello,
I have an Elixir backend that implements a custom protocol over TCP. I want to load test the backend and assess the performance o...
New
Other Trending Topics
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge & Solve.
They are GUI (Emerge) and State management (S...
New
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #blog-post
- #phoenix_html
- #iex
- #graphql
- #ai
- #genstage
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex










First 4 of 4 Posts
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.