have the same (nlog ncomplexity as the optimal priority queue based versions of prim' algorithmbut will be faster than the standard ( prim' algorithm howeverif the graph is highly connectedi the number of edges is near the square of the number of verticesit will have complexity ( log nand be slower than the optimal ( versions of prim' algorithm travelling salesmen and vehicle routing note that all the graph algorithms we have considered so far have had polynomial time complexity there are further graph based problems that are even more complex probably the most well known of these is the travelling salesman problemwhich involves finding the shortest path through graph which visits each node precisely once there are currently no known polynomial time algorithms for solving this since only algorithms with exponential complexity are knownthis makes the travelling salesman problem difficult even for moderately sized ( all capital citiesexercisewrite an algorithm in pseudocode that solves the travelling salesman problemand determine its time complexity variation of the shortest path problem with enormous practical importance in transportation is the vehicle routing problem this involves finding series of routes to service number of customers with fleet of vehicles with minimal costwhere that cost may be the number of vehicles requiredthe total distance coveredor the total driver time required oftenfor practical instancesthere are conflicts between the various objectivesand there is trade-off between the various costs which have to be balanced in such casesa multi-objective optimization approach is required which returns pareto front of non-dominated solutionsi set solutions for which there are no other solutions which are better on all objectives alsoin practicethere are usually various constraints involvedsuch as fixed delivery timewindowsor limited capacity vehiclesthat must be satisfiedand that makes finding good solutions even more difficult since exact solutions to these problems are currently impossible for all but the smallest casesheuristic approaches are usually employedsuch as evolutionary computationwhich deliver solutions that are probably good but cannot be proved to be optimal one popular approach is to maintain whole population of solutionsand use simulated evolution by natural selection to iteratively improve the quality of those solutions that has the additional advantage of being able to generate whole pareto front of solutions rather than just single solution this is currently still very active research area