0
\$\begingroup\$

I wanted to ask whether it is even possible to implement the Bellman-Ford algorithm on a finite state machine.

How can you determine whether a machine will have a finite number of states or not?

Edit: The Bellman-Ford algorithm finds the shortest path between 2 nodes in a set of nodes.

\$\endgroup\$
  • \$\begingroup\$ Is this not graph-searching? \$\endgroup\$ – analogsystemsrf May 7 at 12:49
  • \$\begingroup\$ It is graph searching, are those algorithms difficult to implement on FSM? \$\endgroup\$ – user221368 May 7 at 12:52
  • \$\begingroup\$ stackoverflow.com/questions/37460501/… \$\endgroup\$ – user221368 May 7 at 12:54
  • \$\begingroup\$ I read something here about A* algorithm on FSM, its very similar to bellman ford. I couldnt understand what the commenter wrote about Open and closed sets not bounded in size by a constant \$\endgroup\$ – user221368 May 7 at 12:55
  • \$\begingroup\$ I can imagine a push-down stack is required, which gives a strictly ordered access to the nodes. But even more flexible (random?) access, to nodes and an accumulated-distance of each trail-path, may be needed. There is a hierarchy of "compute machines", and those with just a stack-memory are LOW in the hierarchy.I think Fano wrote a book on compute-machines, under some title. \$\endgroup\$ – analogsystemsrf May 7 at 12:58
2
\$\begingroup\$

Snarky half-answer: Of course you can implement this in a FSM. Imagine an ordinary x86_64 processor sitting in a desktop computer. If I call each of the 2^32 bytes in memory part of my "state", wouldn't you agree that my desktop computer is a FSM?

The Wikipedia page on this algorithm gives a Python implementation, which can run on my computer, so yes. My FSM can implement the Bellman-Ford algorithm.

Now that we've proven it's possible to do with a non-infinite number of states, I'm sure it's possible to do with fewer states.

\$\endgroup\$
  • \$\begingroup\$ Im talking about direct hardware implementation of a FSM, not software implementation of a FSM \$\endgroup\$ – user221368 May 7 at 12:49
  • \$\begingroup\$ Essentially what youre saying is it depend on how much memory you have \$\endgroup\$ – user221368 May 7 at 12:50
  • \$\begingroup\$ @HappyDayYeah Theoretically, any algorithm that can be implemented in a "software" state machine can also be implemented in hardware. What exactly are you looking for? \$\endgroup\$ – Elliot Alderson May 7 at 15:00
  • \$\begingroup\$ How would you represent the states for a machine which implements bellmand ford? \$\endgroup\$ – user221368 May 7 at 18:13