For a computer network, it's useful to know how to get a packet from one host to another across the Internet.
For this challenge, you will print out the shortest route from one host to another on the console.
Even though we're using this to see how packets are routed on a network, the exact same procedure could be used to:
- find how you're connected to a friend of a friend
- route an AI through a level
- etc.
This is what is in the boilerplate:
Take your BFS code and modify it so that each neighbor gets a link back to its parent:
BFS(graph, startVert):
for v of graph.vertexes:
v.color = white
v.parent = null // <-- Add parent initialization
startVert.color = gray
queue.enqueue(startVert)
while !queue.isEmpty():
u = queue[0]
for v of u.neighbors:
if v.color == white:
v.color = gray
v.parent = u // <-- Keep a parent link
queue.enqueue(v)
queue.dequeue()
u.color = black
-
Perform a BFS from the ending vert (host). This will set up all the
parent
pointers across the graph. -
Output the route by following the parent pointers from the starting vert printing the values as you go.
$ node routing.js HostA HostD
HostA --> HostB --> HostD
$ node routing.js HostA HostH
HostA --> HostC --> HostF --> HostH
$ node routing.js HostA HostA
HostA
$ node routing.js HostE HostB
HostE --> HostF --> HostC --> HostA --> HostB