Re: Graph - find a path from A to B with path constraints


p...@xxxxxxxxxxxxx

Hi,

I am given:
Start Point
End Point
Graph showing From City, To City, and Airline or Airline with flight
number
"adjacency list" & "list of nodes"
List of flights (Airline with flight number or just an Airline).
This is to used in getting from A to B.
Order of flights given must be met.

I have to find:
The cities that are to traversed to get from A to B using the
flights given.

Graph will have many connections between nodes and there can be
multiple connections between any 2 ports.

For example the relevant connections in the graph are:
Adelaide Sydney Airline A Flight730
Sydney Bangkok Airline A Flight1
Sydney Bangkok Airline A Flight730
Bangkok London Airline A Flight1
Sydney London Airline A Flight1
London Amsterdam Airline B
Bangkok Amsterdam Airline B

Assume all flight routes have the SAME LENGTH.

You will be given:
Adelaide
Amsterdam
Airline A,Flight730
AirlineA,Flight1
AirlineB


The shortest path would be (which the Dijstra's algorithm would
produce):
Adelaide -> Sydney Airline A Flight730
Sydney -> Bangkok Airline A Flight730
Bangkok -> Amsterdam Airline B

But this does not fit the given flights.

So the correct path would be:
Adelaide -> Sydney Airline A Flight730
Sydney -> Bangkok Airline A Flight1
Bangkok -> London Airline A Flight1
London -> Amsterdam Airline B


Of course this example is simple but the real graph is much more
complicated.

Can you suggest an algorithm to use?
Are there any web sites/newsgroup articles that can assist - ideally
with examples in Oracle's PL/SQL?

Thanks for any help

I think this problme is equal to the assignment problem of a multi
directed graph with resource constraints. Maybe you can search from
google and look for some existence coding such as C++, Java, but
coding of Oracle's PL/SQL maybe very few.

--------------
Best regards,
Zhu

.

Relevant Pages

  • Graph - find a path from A to B with path constraints
    ... Graph showing From City, To City, and Airline or Airline with flight ... List of flights. ... The other complication is that the Graph will have many connections. ...
    (comp.theory)
  • Graph - find a path from A to B with path constraints
    ... Graph showing From City, To City, and Airline or Airline with flight ... List of flights. ...
    (comp.theory)
  • NYT: Ugly Airline Math: Planes Late, Fliers Even Later
    ... Janis Cavinder endured a two-hour delay ... Newark and ended last night with a flight on another airline. ... But with domestic flights running 85 to 90 percent ... About 32 percent of domestic passengers connect from one flight to another ...
    (rec.travel.air)
  • Re: Flying AF?
    ... analyze the available flights, and to determine what my odds were to ... Want to ask the folks there if they are happy? ... folks being laid off from CO, United, and the other many other airline ... Anyone stupid enough to claim that CO serves economy food in FC (and ...
    (rec.travel.air)
  • Re: JFK-Seoul on a 747-400? not!!!!
    ... flights from UT, you went to the authoritative source, the airline in this ... do often show future routes that are not in service yet. ... Future Jetstar routes include service to Mexico and Cuba. ...
    (rec.travel.air)