For the record, this is for a school assignment, however developing algorithms on our own is not the point of this class. Our goal is make something work on real hardware so the professor doesn’t care how we do our research, only that the final result works.
What we have is a graph with weighted edges(the weights being the distances been vertices). Now we’re given information about a small number of vehicles: their current position, the speed that they will travel at and their destination. Given all that, the goal is to send all those vehicles along the shortest path(by time) to their destination, avoiding having the the vehicles crash into one another(vehicles can crash head-on or by having one overtake the other).
It’s not necessary to find the absolute shortest path if that’s not possible, but we would prefer to be able to do that. Are there any algorithms of this type around? I’m aware of Dijkstra’s algorithm and the like but those don’t take collisions into account.
You might be able to find something by looking for disjoint path algorithms. IIRC, those are what the telephone companies use to route calls through the network and avoid collisions.
Ah, thank you ultrafilter, you set me on the right path. This type of problem is described by a flow network. My particular problem is a type of Multi-commodity flow problem.
Can the vehicles voluntarily reduce speed or wait at a node so as to avoid an overtaking crash? And while I’m thinking of it, is passing allowed at the nodes? If the answer to either of those questions is “no”, then there’s no guarantee that a solution exists. For the simplest case, consider a two-node graph with an edge from A to B, a car at A that wants to get to B, and a car at B that wants to get to A.
More generally, do you have any expectation of how dense the cars will be on the graph? If there are known to be relatively few cars, then a good algorithm might start by just finding the best path for each individual vehicle, putting them all together, and checking for collisions, and only worry about them if there are any.
Don’t forget to compensate for the harmonics of Avocado’s Number. Here at the SDMB, we are sworn to refuse homework questions, though some rebels persist. What, your mother didn’t know, or Og forbid, your father? Your own brain is an infinite resource, greater even than Wikipedia.
You don’t believe me, of course. You think that Rysto’s cranium contains nothing of value. It is not true, grasshopper. Hidden in the piles of vidgame ejectementa is actual intelligence. You must find the time to seek it out. I am tired from saying that. Go on without me. I’ll get home okay.
