Dijkstra algorithm program
*&———————————————————————*
*& Report Z_SEARCH_OPTIMAL_FLIGHTS *
*& *
*&———————————————————————*
*& *
*& *
*&———————————————————————*
REPORT z_search_optimal_flights.
TABLES: sflight.
PARAMETERS p_weg RADIOBUTTON GROUP rad1.
PARAMETERS p_preis RADIOBUTTON GROUP rad1.
PARAMETERS p_start TYPE zs_airport.
PARAMETERS p_ziel TYPE zs_airport.
PARAMETERS p_umstz TYPE numc2.
SELECTION-SCREEN SKIP 1.
SELECT-OPTIONS: s_fldate FOR sflight-fldate.
* SPFLI für Flugverbindungen
DATA: lt_spfli TYPE TABLE OF spfli WITH HEADER LINE.
* SFLIGHT für Preise
DATA: lt_sflight TYPE TABLE OF sflight WITH HEADER LINE.
START-OF-SELECTION.
** Daten einlesen, ‘Graph’ bilden
SELECT * FROM spfli INTO TABLE lt_spfli.
SELECT * FROM sflight INTO TABLE lt_sflight.
SORT lt_sflight BY fldate ASCENDING.
* Adjazenzzeile: enthält Flughäfen
* wir gehen davon aus, dass das Kürzel des Flughafens eindeutig ist
* d.h. der Flughafen ist durch das Kürzel eindeutig definiert
* Flughäfen sammeln
DATA: lt_airports TYPE TABLE OF s_fromairp WITH HEADER LINE.
LOOP AT lt_spfli.
MOVE lt_spfli-airpfrom TO lt_airports.
APPEND lt_airports.
MOVE lt_spfli-airpto TO lt_airports.
APPEND lt_airports.
ENDLOOP.
SORT lt_airports.
DELETE ADJACENT DUPLICATES FROM lt_airports.
TYPES: BEGIN OF tl_flights,
distance LIKE spfli-distance,
price LIKE sflight-price,
fldate LIKE sflight-fldate,
carrid LIKE spfli-carrid,
connid LIKE spfli-connid,
END OF tl_flights.
TYPES: BEGIN OF tl_adj,
airpto TYPE s_airport,
flight TYPE tl_flights OCCURS 0,
END OF tl_adj.
TYPES: BEGIN OF t_adj,
airpfrom TYPE s_airport,
dest TYPE tl_adj OCCURS 0,
END OF t_adj.
TYPES: tt_adj TYPE TABLE OF t_adj.
* Adjazenzmatrix
DATA: lt_graph TYPE TABLE OF t_adj.
PERFORM adjazenzmatrix_bilden
TABLES lt_airports lt_spfli lt_sflight lt_graph.
* Priority Queue
TYPES: BEGIN OF t_priority,
airport_from TYPE s_airport,
distance TYPE p DECIMALS 2,
flight TYPE tl_flights,
infinite(1),
END OF t_priority.
DATA: lt_priority TYPE TABLE OF t_priority WITH HEADER LINE.
DATA: lt_priority_save TYPE TABLE OF t_priority WITH HEADER LINE.
PERFORM initialize TABLES lt_airports lt_priority.
lt_priority_save[] = lt_priority[].
DATA: lv_zaehler LIKE sy-tabix.
CLEAR lv_zaehler.
DO.
* Prioritätswarteschlange sichern
lt_priority_save[] = lt_priority[].
DO lv_zaehler TIMES.
READ TABLE lt_priority INDEX 1.
DELETE lt_priority INDEX 1.
ENDDO.
IF NOT lt_priority[] IS INITIAL AND NOT lt_priority-airport_from =
p_ziel.
PERFORM relax TABLES lt_graph lt_priority.
DATA: llv_tabix LIKE sy-tabix.
* geänderte Einträge aus Prioritätswarteschlange
* merken
LOOP AT lt_priority.
llv_tabix = sy-tabix + lv_zaehler.
lt_priority_save = lt_priority.
MODIFY lt_priority_save INDEX llv_tabix.
ENDLOOP.
lt_priority[] = lt_priority_save[].
ELSE.
EXIT.
ENDIF.
ADD 1 TO lv_zaehler.
ENDDO.
DATA: lt_path TYPE TABLE OF tl_flights WITH HEADER LINE.
REFRESH lt_path.
IF lt_priority-airport_from = p_ziel.
PERFORM pfad_rekonstruieren TABLES lt_priority_save lt_path lt_spfli.
ENDIF.
PERFORM liste_ausgeben TABLES lt_path.
STOP.
*&——————————————————————–*
*& Form adjazenzmatrix_bilden
*&——————————————————————–*
* text
*———————————————————————*
* –>PT_AIRPORTStext
* –>PT_SPFLI text
* –>PT_SFLIGHT text
* –>PT_GRAPH text
*———————————————————————*
FORM adjazenzmatrix_bilden
TABLES pt_airports pt_spfli STRUCTURE spfli pt_sflight STRUCTURE sflight
pt_graph TYPE tt_adj.
DATA: wa_graph TYPE t_adj.
DATA: wa_dest TYPE tl_adj.
DATA: wa_flight TYPE tl_flights.
LOOP AT pt_airports.
LOOP AT pt_spfli WHERE airpfrom = pt_airports.
* Bei Startflughafen Selektion für Abflugdatum berücksichtigen
IF pt_spfli-airpfrom = p_start.
LOOP AT pt_sflight WHERE
carrid = pt_spfli-carrid AND
connid = pt_spfli-connid AND
fldate IN s_fldate.
MOVE-CORRESPONDING pt_sflight TO wa_flight.
MOVE-CORRESPONDING pt_spfli TO wa_flight.
APPEND wa_flight TO wa_dest-flight.
CLEAR wa_flight.
ENDLOOP.
ELSE.
LOOP AT pt_sflight WHERE
carrid = pt_spfli-carrid AND
connid = pt_spfli-connid.
MOVE-CORRESPONDING pt_sflight TO wa_flight.
MOVE-CORRESPONDING pt_spfli TO wa_flight.
APPEND wa_flight TO wa_dest-flight.
CLEAR wa_flight.
ENDLOOP.
ENDIF.
IF sy-subrc = 0.
wa_dest-airpto = pt_spfli-airpto.
APPEND wa_dest TO wa_graph-dest.
ENDIF.
CLEAR wa_dest.
ENDLOOP.
IF sy-subrc = 0.
wa_graph-airpfrom = pt_spfli-airpfrom.
APPEND wa_graph TO pt_graph.
ENDIF.
CLEAR wa_graph.
ENDLOOP.
ENDFORM. “adjazenzmatrix_bilden
*&——————————————————————–*
*& Form initialize
*&——————————————————————–*
* text
*———————————————————————*
* –>PT_AIRPORTStext
* –>PT_PRIORITYtext
*———————————————————————*
FORM initialize TABLES pt_airports pt_priority.
DATA wa_priority TYPE t_priority.
DATA llt_priority TYPE TABLE OF t_priority WITH HEADER LINE.
REFRESH llt_priority.
LOOP AT pt_airports.
CLEAR wa_priority.
wa_priority-airport_from = pt_airports.
IF pt_airports NE p_start.
wa_priority-infinite = ‘X’.
ENDIF.
APPEND wa_priority TO llt_priority.
ENDLOOP.
SORT llt_priority BY infinite ASCENDING.
pt_priority[] = llt_priority[].
ENDFORM. “initialize
*&——————————————————————–*
*& Form relax
*&——————————————————————–*
* text
*———————————————————————*
* –>PT_GRAPH text
* –>PT_PRIORITYtext
*———————————————————————*
FORM relax TABLES pt_graph TYPE tt_adj pt_priority.
DATA: lv_date LIKE sflight-fldate.
DATA: lv_time LIKE spfli-arrtime.
DATA llt_priority TYPE TABLE OF t_priority WITH HEADER LINE.
llt_priority[] = pt_priority[].
DATA: wa_dest TYPE tl_adj.
DATA: wa_flight TYPE tl_flights.
DATA: wa_priority LIKE LINE OF lt_priority.
* Knoten (Flughafen) mit höchster Priorität nehmen
READ TABLE llt_priority INDEX 1.
* genaue Aunkunftszeit (und Datum) das Fluges merken
PERFORM determine_arrival_time
USING llt_priority-flight
CHANGING lv_date lv_time.
* Loop über alle Nachfolger (Zielflughäfen mit direkter Verbindung)
READ TABLE pt_graph WITH KEY airpfrom = llt_priority-airport_from.
LOOP AT pt_graph-dest INTO wa_dest.
* Kürzesten bzw. billigsten Flug heraussuchen
CASE ‘X’.
WHEN p_weg.
SORT wa_dest-flight STABLE BY distance ASCENDING.
WHEN p_preis.
SORT wa_dest-flight STABLE BY price ASCENDING.
ENDCASE.
* diesen lesen
PERFORM read_next_flight
TABLES wa_dest-flight USING lv_date lv_time CHANGING wa_flight.
* altes Coding:
* READ TABLE wa_dest-flight INTO wa_flight INDEX 1.
* noch offen: wenn kein Anschlussflug gefunden, Fehler
IF wa_flight IS INITIAL.
ENDIF.
* ‘relaxieren’, Einträge sind in der Priority Queue
DATA: llv_tabix LIKE sy-tabix.
READ TABLE llt_priority INTO wa_priority WITH KEY
airport_from = wa_dest-airpto.
llv_tabix = sy-tabix.
DATA: llv_dist TYPE p DECIMALS 2.
CASE ‘X’.
WHEN p_weg.
llv_dist = llt_priority-distance + wa_flight-distance.
WHEN p_preis.
llv_dist = llt_priority-distance + wa_flight-price.
ENDCASE.
IF ( wa_priority-distance GT llv_dist ) OR ( wa_priority-infinite = ‘X’
).
CLEAR wa_priority-infinite.
wa_priority-distance = llv_dist.
wa_priority-flight = wa_flight.
* nur, wenn der Flughafen noch nicht da war, einsetzen
* Zyklen braucht man nicht zu beachten, da kürzeste Wege gesucht sind
IF llv_tabix GT 0.
MODIFY llt_priority FROM wa_priority INDEX llv_tabix.
ENDIF.
ENDIF.
ENDLOOP.
* Priority Queue neu sortieren
SORT llt_priority BY infinite ASCENDING distance ASCENDING.
pt_priority[] = llt_priority[].
ENDFORM. “relax
*&——————————————————————–*
*& Form pfad_rekonstruieren
*&——————————————————————–*
* text
*———————————————————————*
* –>PT_PRIORITYtext
*———————————————————————*
FORM pfad_rekonstruieren
TABLES pt_priority pt_path pt_spfli STRUCTURE spfli.
DATA llt_priority TYPE TABLE OF t_priority WITH HEADER LINE.
llt_priority[] = pt_priority[].
DATA llt_path TYPE TABLE OF tl_flights WITH HEADER LINE.
* Priority Queue rückwärts lesen, mit Ziel beginnen
READ TABLE llt_priority WITH KEY airport_from = p_ziel.
IF sy-subrc = 0.
llt_path = llt_priority-flight.
INSERT llt_path INDEX 1.
DO.
* Flug einlesen, dabei bekommt man Startflughafen des Fluges
* dies ist der nächste Eintrag in der Priority Queue
LOOP AT pt_spfli WHERE
carrid = llt_path-carrid AND
connid = llt_path-connid.
EXIT.
ENDLOOP.
READ TABLE llt_priority WITH KEY airport_from = pt_spfli-airpfrom.
IF sy-subrc = 0.
llt_path = llt_priority-flight.
IF NOT llt_path IS INITIAL.
INSERT llt_priority-flight INTO llt_path INDEX 1.
ELSE.
EXIT.
ENDIF.
ENDIF.
ENDDO.
ENDIF.
* Tabelle hier noch aufbereiten
pt_path[] = llt_path[].
ENDFORM. “pfad_rekonstruieren
*&——————————————————————–*
*& Form liste_ausgeben
*&——————————————————————–*
* text
*———————————————————————*
* –>PT_PATH text
*———————————————————————*
FORM liste_ausgeben TABLES pt_path.
DATA: llt_path TYPE TABLE OF tl_flights WITH HEADER LINE.
llt_path[] = pt_path[].
DELETE llt_path WHERE fldate IS INITIAL.
LOOP AT llt_path.
CLEAR lt_sflight.
CLEAR lt_spfli.
READ TABLE lt_sflight WITH KEY
carrid = llt_path-carrid
connid = llt_path-connid
fldate = llt_path-fldate.
READ TABLE lt_spfli WITH KEY
carrid = llt_path-carrid
connid = llt_path-connid.
NEW-LINE.
WRITE: llt_path-carrid, llt_path-connid, llt_path-fldate,
lt_spfli-airpfrom, lt_spfli-deptime, lt_spfli-airpto, lt_spfli-arrtime.
ENDLOOP.
* Listausgabe erzwingen, auch wenn nichts gefunden wurde
IF sy-subrc NE 0.
WRITE: ‘Es wurde zu den eingegebenen Daten keine Flugverbindung
gefunden!’.
ENDIF.
ENDFORM. “liste_ausgeben
*&——————————————————————–*
*& Form determine_arrival_time
*&——————————————————————–*
* text
*———————————————————————*
* –>LT_PRIORITYtextGHT
* –>LV_DATE text
* –>LV_TIME text
*———————————————————————*
FORM determine_arrival_time
USING pt_priority-flight CHANGING p_date p_time.
DATA: ls_flight TYPE tl_flights.
ls_flight = pt_priority-flight.
READ TABLE lt_spfli WITH KEY
carrid = ls_flight-carrid
connid = ls_flight-connid.
p_date = ls_flight-fldate + lt_spfli-period.
p_time = lt_spfli-arrtime.
PERFORM add_hours USING p_umstz CHANGING p_date p_time.
ENDFORM. “determine_arrival_time
*&——————————————————————–*
*& Form read_next_flight
*&——————————————————————–*
* text
*———————————————————————*
* –>P_DATE text
* –>P_TIME text
* –>WA_DEST-FLItext
* –>WA_FLIGHT text
*———————————————————————*
FORM read_next_flight
TABLES pwa_dest-flight USING p_date p_time CHANGING pwa_flight.
DATA: llt_flight TYPE TABLE OF tl_flights WITH HEADER LINE.
llt_flight[] = pwa_dest-flight[].
* wir gehen davon aus, dass die Tabelle pwa_dest-flight
* bereits nach dem richtigen Kriterium sortiert ist (Preis / Entfernung)
* nächsten möglichen Anschlussflug suchen
LOOP AT llt_flight.
CLEAR pwa_flight.
READ TABLE lt_spfli WITH KEY
carrid = llt_flight-carrid
connid = llt_flight-connid.
IF sy-subrc = 0.
IF ( ( lt_spfli-deptime GT p_time )
AND ( llt_flight-fldate = p_date ) )
OR ( llt_flight-fldate GT p_date ).
pwa_flight = llt_flight.
EXIT.
ENDIF.
ENDIF.
ENDLOOP.
ENDFORM. “read_next_flight
*&——————————————————————–*
*& Form add_hours
*&——————————————————————–*
* text
*———————————————————————*
* –>P_DATE text
* –>P_TIME text
* –>P_UMSTZ text
*———————————————————————*
FORM add_hours USING p_umstz CHANGING p_date p_time.
* Stunden (und Tage) dazuzählen
CALL FUNCTION ‘END_TIME_DETERMINE’
EXPORTING
duration = p_umstz
unit = ‘H’
IMPORTING
end_date = p_date
end_time = p_time
CHANGING
start_date = p_date
start_time = p_time
EXCEPTIONS
OTHERS = 7.
IF sy-subrc <> 0.
ENDIF.
ENDFORM. “add_hours