The multilabel algorithm has been run on a graph with 6 node

The multi-label algorithm has been run on a graph with 6 nodes (A-F) to find paths that minimize both travel distance and travel time. The set of labels that exist when the algorithm terminates are shown below. a) What is the list of labels at node F that are non-dominated? b) Give the full path from A to F indicated by label number 10.

Solution

Question 4 a) Labels 7,10 and 12 are non-dominated labels at node F. By definition, non dominated lebels are set of labels such that there exists no label with the value of both time and distance less than the given label.

b) The path is A -> D -> F