search

xukai92 / nndijkstra

2 stars 0 forks source link

Output of Dijkstra's (i.e. the learning target of NN) #2

Open xukai92 opened 8 years ago

xukai92 commented 8 years ago

What do we want the for the output of Dijkstra's?

My options:

  1. The length of the shortest path (assuming a start node)
  2. The terminate node of the shortest path (assuming a start node)
  3. Existing shortest path in the graph (or just its length)
yongli-abc commented 8 years ago

What about the input? Dijkstra has many variant implementation, the most common one is used as a single-source shortest path finder, in which case we input a source point, and find the shortest path & distance to every other node.

If we do this implementation, there're usually two output data: an 'distance' array, and a 'pathTo' array.

The distance array acts as a look-up array, storing the numeric value for the shortest distance between source node to every other node.

The pathTo array records the 'predecessor node' of each node, on the shortest path to this node. If we backtrack on this array, we can rebuild the shortest path between the source node and every other node.

Not sure if this is what you want for the NN. But these are the usual outputs from Dijkstra.

xukai92 commented 8 years ago

I guess we can (and also be safe) to start with the most straightforward milestone - just output the a number: the length of the shortest path from the source.

BTW I've discussed this idea with a postdoc and he said I could try but maybe my hypothesis will just fail as NNs may not generalise the boundary. So I guess let's start with the easiest thing and see if NNs can generalise.