groups - Single pair shortest path multiple travelers -

groups - Single pair shortest path multiple travelers -

i'm programming turn based strategy game , have special single pair shortest path problem. have weighted directed graph non-negative non-zero border weights , here catch, multiple travelers, units different motion types traveling group. each border of graph has different weights different units depending on motion type.

normally 1 utilize eg. dijkstras algorithm solve shortest path problem. multiple units moving grouping , different border weights each unit case may optimal path not same optimal path single unit moving alone. can seen the illustration picture reddish , greenish moving s d. optimal path reddish moving lone s-a-d cost of 2 , optimal path greenish moving lone s-c-d cost of 2. in both cases, however, other units motion cost 5 , optimal path, units moving together, s-b-d maximum motion cost of 4.

different amounts of motion points per turn per unit type seems not problem since border weights normalized. formulated linear programme , solved simplex algorithm ? seem have multiple objective functions , minimize maximum. there perhaps simpler solution ?

if want multiple travelers travel in group, need utilize sort of optimization algorithm , find optimum, you've suggested.

on other hand, if don't need optimum whole grouping (which take time), seek using heuristic or approximate optimization algorithm.

since don't know details of game, can't heuristic useful you. could, perhaps, minimize search space bit choosing representative each of grouping (flyer, swimmer, ground unit...), , find optimum group's path of selected units.

groups shortest-path