Shortest path with BFS on graph

Questions / Help
, ,
1

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!

1 Like
2

Upload it somewhere public and put a link here?

3

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:

3 Likes
4

here it is

1 Like
5

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.