当前位置：首页 > news >正文

一种寻路的应用

news 2025/9/22 5:34:55

应用背景

利用长途车进行货物转运的寻路计算。例如从深圳到大连。可以走有很多条长途车的路线。需要根据需求计算出最合适路线。不同的路线的总里程数、总价、需要的时间不一样。客户根据需求进行选择。主要有一些细节：

全国的长途车车站的数据的更新：
包括位置、发车班次时间点、车站间的里程数等等。常用的路线有18000多条

重庆   重庆   重庆万盛客运中心   308   遵义   遵义市长途汽车站
重庆   重庆   重庆万盛客运中心   360   成都   成都北门汽车站
重庆   重庆   重庆渝中长途汽车站   157   武胜   武胜汽车站
重庆   重庆   重庆渝中长途汽车站   340   遵义   遵义市长途汽车站
重庆   重庆   重庆渝中长途汽车站   360   成都   成都北门汽车站
重庆   重庆   重庆渝中长途汽车站   467   巴中   巴中江北客运中心站
重庆   重庆   重庆渝中长途汽车站   502   广元   广元市长途汽车客运站

同城转车的处理
有些城市有多个车站，可以在一个城市里转到另外一个车站，再转运到下一站
使用发车班次时间表进行总时长的计算
预留出合理的时间间隔。例如到达某一站是20:30，但是到下一站的车最晚一班是15:00 点发车。所以只能等第2天的班车。还有的班次可能一周只有2趟车。有时到达某一站是15:00 下一站的发车时间也是15:00 这种就只能等下一班，因为赶不上。

代码实现

初始化

班车路线、城市、车站等

constructor TR_Manager.Create;
begin_result_path := Tlist<TR_Path>.Create;_Dict_Province := TDictionary<Integer, TProvince>.Create();_Dict_City := TDictionary<Integer, TCity>.Create();_Dict_City_Name := TDictionary<string, TCity>.Create();_ProvinceList := Tlist<TProvince>.Create();_StationList := Tlist<TStation>.Create();_Dict_Station := TDictionary<string, TStation>.Create();_StationPathList := Tlist<TStation_Path>.Create();_Dict_CityID_Station := TDictionary < Integer, Tlist < TStation >>.Create();_Dict_CityID_Xian_Station := TDictionary < Integer, TDictionary < string,Tlist<TStation> >>.Create(); // hfg 2016-07-23_StationPathNodeList := Tlist<TStation_Path_Node>.Create();_Dict_Station_Path_Node := TDictionary<TStation, TStation_Path_Node>.Create();_Dict_CityID_Path_Node := TDictionary < Integer, Tlist < TStation_Path_Node>>.Create();_Node_Tmp := Tlist<TStation_Path_Node>.Create();_Node_Tmp_2 := Tlist<TStation_Path_Node>.Create();_Node_Tmp_before_end := Tlist<TStation_Path_Node>.Create();
end;

寻路

StationName_Begin: 起点车站

Station_End: 终点车站

max_step: Integer = 6; 最大转车次数

allow_same_city: boolean = false 是否允许同城转运

function TR_Manager.get_path_quick(StationName_Begin: string;Station_End: Tlist<TStation>; max_step: Integer = 6;allow_same_city: boolean = false): boolean;
varStation: TStation;node_root, node, node_next: TStation_Path_Node;i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,Node_Tmp_before_end_count: Integer;path: TR_Path;list: Tlist;city_station_list: Tlist<TStation_Path_Node>;
beginResult := false;clear_result_path();if Station_End = nil thenexit;if Station_End.Count <= 0 thenexit;if not(_Dict_Station.TryGetValue(StationName_begin, Station)) thenexit;if Station.CityID = Station_End[0].CityID thenbeginpath := TR_Path.Create;path.Mileage := 0;path.step := 1;path.StationList.Add(Station);for i := 0 to Station_End.Count - 1 dobeginif Station_End[i].Name <> Station.Name thenbeginpath.StationList.Add(Station_End[i]);Break;end;end;if path.StationList.Count < 2 thenpath.StationList.Add(Station);_result_path.Add(path);end;if not(_Dict_Station_Path_Node.TryGetValue(Station, node_root)) thenexit;for i := 0 to _StationPathNodeList.Count - 1 do_StationPathNodeList[i].reset();node_root.set_Step(0);_Node_Tmp[0] := node_root;Node_Tmp_Count := 1;Node_Tmp_before_end_count := 0;for i := 0 to Station_End.Count - 1 dobeginif _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) thennode.set_is_before_end();end;for step := 1 to max_step dobeginNode_Tmp_2_Count := 0;for i := 0 to Node_Tmp_Count - 1 dobegintrynode := _Node_Tmp[i];if (node.is_before_end) thenbegin_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;inc(Node_Tmp_before_end_count);if step > 1 thenContinue;end;for k := 0 to node.Next_Station.Count - 1 dobeginnode_next := node.Next_Station[k].Station_Node_Next;if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);endelsebeginif (node_next.step = step) and (step > 1) thenbeginif node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileagethenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;end;end;end;end;if allow_same_city thenbeginif _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,city_station_list) thenbeginfor k := 0 to city_station_list.Count - 1 dobeginnode_next := city_station_list[k];if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + 0;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);end;end;end;end;exceptNode_Tmp_2_Count := Node_Tmp_2_Count - 1;end;end;Node_Tmp_Count := 0;for i := 0 to Node_Tmp_2_Count - 1 dobeginif _Node_Tmp_2[i].is_on_path thenbeginif True thenif Node_Tmp_Count < _Node_Tmp.Count then_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]else_Node_Tmp.Add(_Node_Tmp_2[i]);inc(Node_Tmp_Count);end;end;end;list := Tlist.Create();for i := 0 to Node_Tmp_before_end_count - 1 dobeginpath := TR_Path.Create;node := _Node_Tmp_before_end[i];path.Mileage := node.path_mileage + node.to_end_mileage;path.StationList.Add(node.end_Node.Station);path.StationList.Add(node.Station);node_next := node.Path_Prior_Station;for step := 1 to max_step + 1 dobeginif node_next = nil thenBreak;path.StationList.Add(node_next.Station);if node_next.step <= 0 thenBreak;node_next := node_next.Path_Prior_Stationend;path.StationList.Reverse();list.Add(path);end;list.Sort(@ComparePath_city);for i := 0 to list.Count - 1 do_result_path.Add(list[i]);FreeAndNil(list);Result := _result_path.Count > 0;
end;

操作说明

1、登陆时选择“宝安汽车站”

发布一条到北京的信息

在“深圳”里可以看到刚增加的信息

切换到“湖北武汉”，也可以看到这条信息

切换到“湖北武汉”，也可以看到这条信息

全部代码

unit U_city_manager;interfaceusesSystem.SysUtils, System.Types, System.Classes, Generics.Collections;typeTCounty = classprivate_Name: string;_CityID: Integer;publicconstructor Create;destructor Destroy; override;property Name: string read _Name write _Name;property CityID: Integer read _CityID write _CityID;end;TProvince = class;TCity = classprivate_ID: Integer;_Name: string;_Code: Integer;_TelCode: Integer;_CountyList: Tlist<TCounty>;Province: TProvince;procedure clear_CountyList();publicconstructor Create;destructor Destroy; override;property CountyList: Tlist<TCounty> read _CountyList;property ID: Integer read _ID write _ID;property Name: string read _Name write _Name;property Code: Integer read _Code write _Code;property TelCode: Integer read _TelCode write _TelCode;end;TProvince = classprivate_ID: Integer;_Name: string;_CardCode: string;_CityList: Tlist<TCity>;procedure clear_CityList();publicconstructor Create;destructor Destroy; override;property CityList: Tlist<TCity> read _CityList;property ID: Integer read _ID write _ID;property Name: string read _Name write _Name;property CardCode: string read _CardCode write _CardCode;end;TStation = classprivate_ProvinceName: string;_CityID: Integer;_CityName: string;_Name: string;_xian: string; // hfg 2016-07-23_address_id: Integer;publicconstructor Create;destructor Destroy; override;property ProvinceName: string read _ProvinceName write _ProvinceName;property CityID: Integer read _CityID write _CityID;property CityName: string read _CityName write _CityName;property Name: string read _Name write _Name;property xian: string read _xian write _xian; // hfg 2016-07-23property address_id: Integer read _address_id write _address_id;end;TStation_Path = classprivate_Station_Begin: TStation;_Station_End: TStation;_Mileage: Integer;publicconstructor Create;destructor Destroy; override;property Station_Begin: TStation read _Station_Begin write _Station_Begin;property Station_End: TStation read _Station_End write _Station_End;property Mileage: Integer read _Mileage write _Mileage;end;TStation_Path_Node = class;TStation_Next = classprivate_Station_Node_Next: TStation_Path_Node;_Mileage: Integer;publicconstructor Create;destructor Destroy; override;property Station_Node_Next: TStation_Path_Node read _Station_Node_Nextwrite _Station_Node_Next;property Mileage: Integer read _Mileage write _Mileage;end;TStation_Path_Node = classprivate_Station: TStation;_Next_Station: Tlist<TStation_Next>;_Prior_Station: Tlist<TStation_Next>;_is_on_path: boolean;_is_end: boolean;_step: Integer;_Path_Prior_Station: TStation_Path_Node;_path_mileage: Integer;_is_before_end: boolean;_end_Node: TStation_Path_Node;_to_end_mileage: Integer;procedure clear_Next_Station();procedure clear_Prior_Station();publicconstructor Create;destructor Destroy; override;procedure add_next(next_node: TStation_Path_Node; Mileage: Integer);procedure add_Prior(p_node: TStation_Path_Node; Mileage: Integer);property Station: TStation read _Station write _Station;property Next_Station: Tlist<TStation_Next> read _Next_Stationwrite _Next_Station;property is_on_path: boolean read _is_on_path;property is_end: boolean read _is_end;property step: Integer read _step;property path_mileage: Integer read _path_mileage write _path_mileage;property Path_Prior_Station: TStation_Path_Node read _Path_Prior_Stationwrite _Path_Prior_Station;property is_before_end: boolean read _is_before_end;property to_end_mileage: Integer read _to_end_mileage write _to_end_mileage;property end_Node: TStation_Path_Node read _end_Node;procedure reset();procedure set_Step(v: Integer);procedure set_is_before_end();end;TR_Path = classpublicstep: Integer;Mileage: Integer;StationList: Tlist<TStation>;publicconstructor Create;destructor Destroy; override;function get_txt(): string;function get_txt_with_city(): string;end;TR_Manager = classprivate_ProvinceList: Tlist<TProvince>;_Dict_Province: TDictionary<Integer, TProvince>;_Dict_City: TDictionary<Integer, TCity>;_Dict_City_Name: TDictionary<string, TCity>;_StationList: Tlist<TStation>;_Dict_Station: TDictionary<string, TStation>;_Dict_CityID_Station: TDictionary<Integer, Tlist<TStation>>;_Dict_CityID_Xian_Station: TDictionary<Integer, TDictionary<string, Tlist<TStation>>>;// hfg 2016-07-23_StationPathList: Tlist<TStation_Path>;_StationPathNodeList: Tlist<TStation_Path_Node>;_Dict_Station_Path_Node: TDictionary<TStation, TStation_Path_Node>;_Dict_CityID_Path_Node: TDictionary<Integer, Tlist<TStation_Path_Node>>;_Node_Tmp: Tlist<TStation_Path_Node>;_Node_Tmp_2: Tlist<TStation_Path_Node>;_Node_Tmp_before_end: Tlist<TStation_Path_Node>;_result_path: Tlist<TR_Path>;procedure clear_result_path();procedure clear_ProvinceList();procedure clear_StationList();procedure clear_StationPathList();procedure clear_StationPathNodeList();procedure clear_Dict_CityID_Xian_Station(); // hfg 2016-07-23procedure make_StationPathNodeList();publicconstructor Create;destructor Destroy; override;property ProvinceList: Tlist<TProvince> read _ProvinceList;property result_path: Tlist<TR_Path> read _result_path;procedure load_Province(fn: string);procedure load_Province_sl(sl: TStringList);procedure load_City(fn: string);procedure load_City_sl(sl: TStringList);procedure load_County(fn: string);procedure load_Path(fn: string);procedure load_Path_new(fn: string);procedure load_Path_new_sl(sl: TStringList); // 2016-10-03procedure load_xian(fn: string); // hfg 2016-07-23function get_Province_by_id(ID: Integer): TProvince;function get_City_by_id(ID: Integer): TCity;function get_City_by_name(ProvinceName, city_name: string): TCity;function get_City_by_full_name(full_city_name: string): TCity;function get_or_add_Station(ProvinceName, CityName, Name: string): TStation;function get_or_add_Station_new(city_id, Name, xian: string): TStation;procedure get_station_by_city_id(city_id: Integer;var list: Tlist<TStation>);procedure get_station_by_city_id_xian(city_id: Integer; xian: string;var list: Tlist<TStation>); // hfg 2016-07-23function get_path_quick(StationName_begin: string;Station_End: Tlist<TStation>; max_step: Integer = 6;allow_same_city: boolean = false): boolean;function get_path_quick_ex(Station_Begin: Tlist<TStation>;Station_End: Tlist<TStation>; max_step: Integer = 6;allow_same_city: boolean = false): boolean; // 2016-10-01function get_StationList: Tlist<TStation>;procedure save_Station(fn: string);property StationPathList: Tlist<TStation_Path> read _StationPathList;end;implementationuses u_address_def;function get_Province_ID_from_City_Code(v: Integer): Integer;
beginResult := v div 100;
end;function ComparePath_city(Item1, Item2: TR_Path): Integer;
beginResult := Item1.StationList.Count - Item2.StationList.Count;if Result = 0 thenResult := Item1.Mileage - Item2.Mileage;end;{ TR_Manager }
procedure TR_Manager.clear_Dict_CityID_Xian_Station; // hfg 2016-07-23
varpair: TPair<Integer, TDictionary<string, Tlist<TStation>>>;pair2: TPair<string, Tlist<TStation>>;
beginfor pair in _Dict_CityID_Xian_Station dobeginfor pair2 in pair.Value dobeginpair2.Value.Freeend;pair.Value.Free;end;_Dict_CityID_Xian_Station.Clear();
end;procedure TR_Manager.clear_ProvinceList;
vari: Integer;
beginfor i := 0 to _ProvinceList.Count - 1 do_ProvinceList[i].Free;_ProvinceList.Clear();_Dict_Province.Clear();_Dict_City.Clear();_Dict_City_Name.Clear();
end;procedure TR_Manager.clear_result_path;
vari: Integer;
beginfor i := 0 to _result_path.Count - 1 do_result_path[i].Free;_result_path.Clear();
end;procedure TR_Manager.clear_StationList;
vari: Integer;pair: TPair<Integer, Tlist<TStation>>;
begin_Dict_Station.Clear();for i := 0 to _StationList.Count - 1 do_StationList[i].Free;_StationList.Clear();for pair in _Dict_CityID_Station dobeginpair.Value.Free;end;_Dict_CityID_Station.Clear();
end;procedure TR_Manager.clear_StationPathList;
vari: Integer;
beginfor i := 0 to _StationPathList.Count - 1 do_StationPathList[i].Free;_StationPathList.Clear();
end;procedure TR_Manager.clear_StationPathNodeList;
vari: Integer;pair: TPair<Integer, Tlist<TStation_Path_Node>>;
begin_Dict_Station_Path_Node.Clear();for pair in _Dict_CityID_Path_Node dobeginpair.Value.Free;end;_Dict_CityID_Path_Node.Clear();for i := 0 to _StationPathNodeList.Count - 1 do_StationPathNodeList[i].Free;_StationPathNodeList.Clear();
end;constructor TR_Manager.Create;
begin_result_path := Tlist<TR_Path>.Create;_Dict_Province := TDictionary<Integer, TProvince>.Create();_Dict_City := TDictionary<Integer, TCity>.Create();_Dict_City_Name := TDictionary<string, TCity>.Create();_ProvinceList := Tlist<TProvince>.Create();_StationList := Tlist<TStation>.Create();_Dict_Station := TDictionary<string, TStation>.Create();_StationPathList := Tlist<TStation_Path>.Create();_Dict_CityID_Station := TDictionary < Integer, Tlist < TStation >>.Create();_Dict_CityID_Xian_Station := TDictionary < Integer, TDictionary < string,Tlist<TStation> >>.Create(); // hfg 2016-07-23_StationPathNodeList := Tlist<TStation_Path_Node>.Create();_Dict_Station_Path_Node := TDictionary<TStation, TStation_Path_Node>.Create();_Dict_CityID_Path_Node := TDictionary < Integer, Tlist < TStation_Path_Node>>.Create();_Node_Tmp := Tlist<TStation_Path_Node>.Create();_Node_Tmp_2 := Tlist<TStation_Path_Node>.Create();_Node_Tmp_before_end := Tlist<TStation_Path_Node>.Create();
end;destructor TR_Manager.Destroy;
beginclear_result_path();FreeAndNil(_result_path);clear_ProvinceList();FreeAndNil(_ProvinceList);FreeAndNil(_Dict_Province);FreeAndNil(_Dict_City);FreeAndNil(_Dict_City_Name);clear_StationList();FreeAndNil(_StationList);FreeAndNil(_Dict_Station);clear_StationPathList();FreeAndNil(_StationPathList);clear_StationPathNodeList();FreeAndNil(_StationPathNodeList);FreeAndNil(_Node_Tmp);FreeAndNil(_Node_Tmp_2);FreeAndNil(_Node_Tmp_before_end);clear_Dict_CityID_Xian_Station(); // hfg 2016-07-23FreeAndNil(_Dict_CityID_Xian_Station); // hfg 2016-07-23inherited;
end;function TR_Manager.get_City_by_full_name(full_city_name: string): TCity;
beginif not _Dict_City_Name.TryGetValue(full_city_name, Result) thenResult := nil;
end;function TR_Manager.get_City_by_id(ID: Integer): TCity;
beginif not _Dict_City.TryGetValue(ID, Result) thenResult := nil;
end;function TR_Manager.get_City_by_name(ProvinceName, city_name: string): TCity;
beginif not _Dict_City_Name.TryGetValue(ProvinceName + city_name, Result) thenResult := nil;
end;function TR_Manager.get_or_add_Station(ProvinceName, CityName, Name: string): TStation;
varcity: TCity;Station: TStation;CityID: Integer;l: Tlist<TStation>;
beginResult := nil;if _Dict_Station.TryGetValue(Name, Result) thenexit;if _Dict_City_Name.TryGetValue(ProvinceName + CityName, city) thenCityID := city.IDelsebeginCityID := 9999999;exit;end;Station := TStation.Create;Station.ProvinceName := ProvinceName;Station.CityID := CityID;Station.CityName := CityName;Station.Name := Name;_StationList.Add(Station);_Dict_Station.AddOrSetValue(Station.Name, Station);if (not _Dict_CityID_Station.TryGetValue(CityID, l)) thenbeginl := Tlist<TStation>.Create();_Dict_CityID_Station.AddOrSetValue(CityID, l);end;l.Add(Station);Result := Station;
end;function TR_Manager.get_or_add_Station_new(city_id, Name, xian: string): TStation;
varcity: TCity;Station: TStation;CityID: Integer;l: Tlist<TStation>;
beginResult := nil;if _Dict_Station.TryGetValue(Name, Result) thenexit;CityID := strtointdef(city_id, 9999999);city := get_City_by_id(CityID);if city = nil thenexit;Station := TStation.Create;Station.ProvinceName := city.Province._Name;Station.CityID := CityID;Station.CityName := city.Name;Station.Name := Name;Station.xian := xian;Station.address_id := get_city_xian_id(CityID, xian);_StationList.Add(Station);_Dict_Station.AddOrSetValue(Station.Name, Station);if (not _Dict_CityID_Station.TryGetValue(CityID, l)) thenbeginl := Tlist<TStation>.Create();_Dict_CityID_Station.AddOrSetValue(CityID, l);end;l.Add(Station);Result := Station;
end;function TR_Manager.get_path_quick(StationName_begin: string;Station_End: Tlist<TStation>; max_step: Integer = 6;allow_same_city: boolean = false): boolean;
varStation: TStation;node_root, node, node_next: TStation_Path_Node;i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,Node_Tmp_before_end_count: Integer;path: TR_Path;list: Tlist;city_station_list: Tlist<TStation_Path_Node>;
beginResult := false;clear_result_path();if Station_End = nil thenexit;if Station_End.Count <= 0 thenexit;if not(_Dict_Station.TryGetValue(StationName_begin, Station)) thenexit;if Station.CityID = Station_End[0].CityID thenbeginpath := TR_Path.Create;path.Mileage := 0;path.step := 1;path.StationList.Add(Station);for i := 0 to Station_End.Count - 1 dobeginif Station_End[i].Name <> Station.Name thenbeginpath.StationList.Add(Station_End[i]);Break;end;end;if path.StationList.Count < 2 thenpath.StationList.Add(Station);_result_path.Add(path);end;if not(_Dict_Station_Path_Node.TryGetValue(Station, node_root)) thenexit;for i := 0 to _StationPathNodeList.Count - 1 do_StationPathNodeList[i].reset();node_root.set_Step(0);_Node_Tmp[0] := node_root;Node_Tmp_Count := 1;Node_Tmp_before_end_count := 0;for i := 0 to Station_End.Count - 1 dobeginif _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) thennode.set_is_before_end();end;for step := 1 to max_step dobeginNode_Tmp_2_Count := 0;for i := 0 to Node_Tmp_Count - 1 dobegintrynode := _Node_Tmp[i];if (node.is_before_end) thenbegin_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;inc(Node_Tmp_before_end_count);if step > 1 thenContinue;end;for k := 0 to node.Next_Station.Count - 1 dobeginnode_next := node.Next_Station[k].Station_Node_Next;if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);endelsebeginif (node_next.step = step) and (step > 1) thenbeginif node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileagethenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;end;end;end;end;if allow_same_city thenbeginif _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,city_station_list) thenbeginfor k := 0 to city_station_list.Count - 1 dobeginnode_next := city_station_list[k];if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + 0;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);end;end;end;end;exceptNode_Tmp_2_Count := Node_Tmp_2_Count - 1;end;end;Node_Tmp_Count := 0;for i := 0 to Node_Tmp_2_Count - 1 dobeginif _Node_Tmp_2[i].is_on_path thenbeginif True thenif Node_Tmp_Count < _Node_Tmp.Count then_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]else_Node_Tmp.Add(_Node_Tmp_2[i]);inc(Node_Tmp_Count);end;end;end;list := Tlist.Create();for i := 0 to Node_Tmp_before_end_count - 1 dobeginpath := TR_Path.Create;node := _Node_Tmp_before_end[i];path.Mileage := node.path_mileage + node.to_end_mileage;path.StationList.Add(node.end_Node.Station);path.StationList.Add(node.Station);node_next := node.Path_Prior_Station;for step := 1 to max_step + 1 dobeginif node_next = nil thenBreak;path.StationList.Add(node_next.Station);if node_next.step <= 0 thenBreak;node_next := node_next.Path_Prior_Stationend;path.StationList.Reverse();list.Add(path);end;list.Sort(@ComparePath_city);for i := 0 to list.Count - 1 do_result_path.Add(list[i]);FreeAndNil(list);Result := _result_path.Count > 0;
end;function TR_Manager.get_path_quick_ex(Station_Begin,Station_End: Tlist<TStation>; max_step: Integer;allow_same_city: boolean): boolean;
varStation: TStation;node_root, node, node_next: TStation_Path_Node;m, i, k, step, Node_Tmp_Count, Node_Tmp_2_Count,Node_Tmp_before_end_count: Integer;path: TR_Path;list: Tlist;city_station_list: Tlist<TStation_Path_Node>;
beginResult := false;clear_result_path();if Station_Begin = nil thenexit;if Station_Begin.Count <= 0 thenexit;if Station_End = nil thenexit;if Station_End.Count <= 0 thenexit;for m := 0 to Station_Begin.Count - 1 dobeginStation := Station_Begin[m];if Station.CityID = Station_End[0].CityID thenbeginpath := TR_Path.Create;path.Mileage := 0;path.step := 1;path.StationList.Add(Station);for i := 0 to Station_End.Count - 1 dobeginif Station_End[i].Name <> Station.Name thenbeginpath.StationList.Add(Station_End[i]);Break;end;end;if path.StationList.Count < 2 thenpath.StationList.Add(Station);_result_path.Add(path);end;end;for i := 0 to _StationPathNodeList.Count - 1 do_StationPathNodeList[i].reset();Node_Tmp_Count := 0;for m := 0 to Station_Begin.Count - 1 dobeginStation := Station_Begin[m];if (_Dict_Station_Path_Node.TryGetValue(Station, node_root)) thenbegin_Node_Tmp[Node_Tmp_Count] := node_root;node_root.set_Step(0);Node_Tmp_Count := Node_Tmp_Count + 1;end;end;if Node_Tmp_Count = 0 thenexit;Node_Tmp_before_end_count := 0;for i := 0 to Station_End.Count - 1 dobeginif _Dict_Station_Path_Node.TryGetValue(Station_End[i], node) thennode.set_is_before_end();end;for step := 1 to max_step dobeginNode_Tmp_2_Count := 0;for i := 0 to Node_Tmp_Count - 1 dobegintrynode := _Node_Tmp[i];if (node.is_before_end) thenbegin_Node_Tmp_before_end[Node_Tmp_before_end_count] := node;inc(Node_Tmp_before_end_count);if step > 1 thenContinue;end;for k := 0 to node.Next_Station.Count - 1 dobeginnode_next := node.Next_Station[k].Station_Node_Next;if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);endelsebeginif (node_next.step = step) and (step > 1) thenbeginif node.path_mileage + node.Next_Station[k].Mileage < node_next.path_mileagethenbeginnode_next.path_mileage := node.path_mileage + node.Next_Station[k].Mileage;node_next.Path_Prior_Station := node;end;end;end;end;if allow_same_city thenbeginif _Dict_CityID_Path_Node.TryGetValue(node.Station.CityID,city_station_list) thenbeginfor k := 0 to city_station_list.Count - 1 dobeginnode_next := city_station_list[k];if node_next.is_end thenContinue;if not node_next.is_on_path thenbeginnode_next.path_mileage := node.path_mileage + 0;node_next.Path_Prior_Station := node;node_next.set_Step(step);if Node_Tmp_2_Count < _Node_Tmp_2.Count then_Node_Tmp_2[Node_Tmp_2_Count] := node_nextelse_Node_Tmp_2.Add(node_next);inc(Node_Tmp_2_Count);end;end;end;end;exceptNode_Tmp_2_Count := Node_Tmp_2_Count - 1;end;end;Node_Tmp_Count := 0;for i := 0 to Node_Tmp_2_Count - 1 dobeginif _Node_Tmp_2[i].is_on_path thenbeginif True thenif Node_Tmp_Count < _Node_Tmp.Count then_Node_Tmp[Node_Tmp_Count] := _Node_Tmp_2[i]else_Node_Tmp.Add(_Node_Tmp_2[i]);inc(Node_Tmp_Count);end;end;end;list := Tlist.Create();for i := 0 to Node_Tmp_before_end_count - 1 dobeginpath := TR_Path.Create;node := _Node_Tmp_before_end[i];path.Mileage := node.path_mileage + node.to_end_mileage;path.StationList.Add(node.end_Node.Station);path.StationList.Add(node.Station);node_next := node.Path_Prior_Station;for step := 1 to max_step + 1 dobeginif node_next = nil thenBreak;path.StationList.Add(node_next.Station);if node_next.step <= 0 thenBreak;node_next := node_next.Path_Prior_Stationend;path.StationList.Reverse();list.Add(path);end;list.Sort(@ComparePath_city);for i := 0 to list.Count - 1 do_result_path.Add(list[i]);FreeAndNil(list);Result := _result_path.Count > 0;end;function TR_Manager.get_Province_by_id(ID: Integer): TProvince;
beginif not _Dict_Province.TryGetValue(ID, Result) thenResult := nil;
end;function TR_Manager.get_StationList: Tlist<TStation>;
beginResult := _StationList;
end;procedure TR_Manager.get_station_by_city_id(city_id: Integer;var list: Tlist<TStation>);
beginif not(_Dict_CityID_Station.TryGetValue(city_id, list)) thenlist := nil;
end;procedure TR_Manager.get_station_by_city_id_xian(city_id: Integer; xian: string;var list: Tlist<TStation>); // hfg 2016-07-23
vardict: TDictionary<string, Tlist<TStation>>;
beginif not _Dict_CityID_Xian_Station.TryGetValue(city_id, dict) thenbeginlist := nil;exit;end;if not dict.TryGetValue(xian, list) thenbeginlist := nil;exit;end;
end;procedure TR_Manager.load_City(fn: string);
varsl: TStringList;
beginsl := TStringList.Create;sl.LoadFromFile(fn);load_City_sl(sl);FreeAndNil(sl);
end;procedure TR_Manager.load_City_sl(sl: TStringList);
vari, pid: Integer;ss: TArray<String>;c: TCity;p: TProvince;
begin_Dict_City.Clear();_Dict_City_Name.Clear();for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 3 thenbeginc := TCity.Create;c.ID := strtointdef(ss[0], 0);c.Name := ss[1];if length(ss) = 4 thenbeginc.Code := strtointdef(ss[2], 0);c.TelCode := strtointdef(ss[3], 0);pid := get_Province_ID_from_City_Code(c.Code);endelsebeginpid := strtointdef(ss[2], 0);end;p := get_Province_by_id(pid);if p <> nil thenbeginp.CityList.Add(c);_Dict_City.AddOrSetValue(c.ID, c);_Dict_City_Name.AddOrSetValue(p.Name + c.Name, c);end;c.Province := p;end;SetLength(ss, 0);end;
end;procedure TR_Manager.load_County(fn: string);
vari, pid: Integer;sl: TStringList;ss: TArray<String>;city: TCity;county: TCounty;
beginsl := TStringList.Create;sl.LoadFromFile(fn);for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 2 thenbegincounty := TCounty.Create;county.CityID := strtointdef(ss[0], 0);county.Name := ss[1];city := get_City_by_id(pid);if city <> nil thenbegincity.CountyList.Add(county);end;end;SetLength(ss, 0);end;FreeAndNil(sl);
end;procedure TR_Manager.load_Path(fn: string);
vari, m: Integer;sl: TStringList;ss: TArray<String>;s_begin, s_end: TStation;sp: TStation_Path;
beginclear_StationList;clear_StationPathList;sl := TStringList.Create;sl.LoadFromFile(fn);for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 5 thenbeginget_or_add_Station(ss[0], ss[1], ss[2]);end;SetLength(ss, 0);end;sl.LoadFromFile(fn);for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 5 thenbeginif (_Dict_Station.TryGetValue(ss[2], s_begin)) and(_Dict_Station.TryGetValue(ss[5], s_end)) thenbeginm := Round(strtointdef(ss[3], 0));if m > 0 thenbeginsp := TStation_Path.Create;sp.Station_Begin := s_begin;sp.Station_End := s_end;sp.Mileage := m;_StationPathList.Add(sp);endelsebeginend;endelsebeginend;end;SetLength(ss, 0);end;FreeAndNil(sl);make_StationPathNodeList();
end;procedure TR_Manager.load_Path_new(fn: string);
varsl: TStringList;
begin// 2016-10-03sl := TStringList.Create;sl.LoadFromFile(fn);load_Path_new_sl(sl);FreeAndNil(sl);
end;procedure TR_Manager.load_Path_new_sl(sl: TStringList);
vari, m: Integer;ss: TArray<String>;s_begin, s_end: TStation;sp: TStation_Path;
begin// 2016-10-03clear_StationList;clear_StationPathList;for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 6 thenbeginget_or_add_Station_new(ss[0], ss[1], ss[2]);end;SetLength(ss, 0);end;for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 5 thenbeginif (_Dict_Station.TryGetValue(ss[1], s_begin)) and(_Dict_Station.TryGetValue(ss[5], s_end)) thenbeginm := Round(strtointdef(ss[3], 0));if m > 0 thenbeginsp := TStation_Path.Create;sp.Station_Begin := s_begin;sp.Station_End := s_end;sp.Mileage := m;_StationPathList.Add(sp);endelsebeginend;endelsebeginend;end;SetLength(ss, 0);end;make_StationPathNodeList();
end;procedure TR_Manager.load_Province(fn: string);
varsl: TStringList;
beginsl := TStringList.Create;sl.LoadFromFile(fn);load_Province_sl(sl);FreeAndNil(sl);
end;procedure TR_Manager.load_Province_sl(sl: TStringList);
vari: Integer;ss: TArray<String>;p: TProvince;
beginclear_ProvinceList();for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) < 0 thenContinue;if length(ss) >= 2 thenbeginp := TProvince.Create;p.ID := strtointdef(ss[0], 0);p.Name := ss[1];if length(ss) >= 3 thenp.CardCode := ss[2];_ProvinceList.Add(p);_Dict_Province.AddOrSetValue(p.ID, p);end;SetLength(ss, 0);end;
end;procedure TR_Manager.load_xian(fn: string); // hfg 2016-07-23
vari: Integer;sl: TStringList;ss: TArray<String>;Station: TStation;dict: TDictionary<string, Tlist<TStation>>;list: Tlist<TStation>;pair: TPair<string, TStation>;procedure set_xian(v: string);beginif Station.xian = '' thenStation.xian := v;end;beginclear_Dict_CityID_Xian_Station();sl := TStringList.Create;sl.LoadFromFile(fn);sl.LoadFromFile(fn);for i := 0 to sl.Count - 1 dobeginss := sl[i].Split([#9]);if length(ss) = 2 thenbeginif _Dict_Station.TryGetValue(ss[0], Station) thenbeginset_xian(ss[1]);end;end;SetLength(ss, 0);end;for pair in _Dict_Station dobeginStation := pair.Value;if Station.xian <> '' thenbeginif not _Dict_CityID_Xian_Station.TryGetValue(Station.CityID, dict) thenbegindict := TDictionary < string, Tlist < TStation >> .Create();_Dict_CityID_Xian_Station.AddOrSetValue(Station.CityID, dict);end;if not dict.TryGetValue(Station.xian, list) thenbeginlist := Tlist<TStation>.Create();dict.AddOrSetValue(Station.xian, list);end;list.Add(Station);end;end;FreeAndNil(sl);
end;procedure TR_Manager.make_StationPathNodeList;
vari, cid: Integer;p, p2: TStation_Path_Node;c_list: Tlist<TStation_Path_Node>;
begin_Node_Tmp.Clear();clear_StationPathNodeList();for i := 0 to _StationList.Count - 1 dobeginp := TStation_Path_Node.Create;p.Station := _StationList[i];_Dict_Station_Path_Node.AddOrSetValue(p.Station, p);_StationPathNodeList.Add(p);_Node_Tmp.Add(nil);_Node_Tmp_2.Add(nil);_Node_Tmp_before_end.Add(nil);cid := _StationList[i].CityID;if not _Dict_CityID_Path_Node.TryGetValue(cid, c_list) thenbeginc_list := Tlist<TStation_Path_Node>.Create;_Dict_CityID_Path_Node.AddOrSetValue(cid, c_list);end;c_list.Add(p);end;for i := 0 to _StationPathList.Count - 1 dobeginif (_Dict_Station_Path_Node.TryGetValue(_StationPathList[i].Station_Begin,p)) and (_Dict_Station_Path_Node.TryGetValue(_StationPathList[i].Station_End, p2)) thenbeginp.add_next(p2, _StationPathList[i].Mileage);p2.add_Prior(p, _StationPathList[i].Mileage);end;end;end;procedure TR_Manager.save_Station(fn: string);
vari: Integer;sl: TStringList;s: string;Station: TStation;
beginsl := TStringList.Create;for i := 0 to _StationList.Count - 1 dobeginStation := _StationList[i];if i = 0 thens := 'select ' + Station.CityID.ToString() + ' as  CityID,' +QuotedStr(Station.Name) + ' as station'elses := 'union select ' + Station.CityID.ToString() + ',' +QuotedStr(Station.Name);sl.Add(s);end;sl.SaveToFile(fn);
end;{ TProvince }procedure TProvince.clear_CityList;
vari: Integer;
beginfor i := 0 to _CityList.Count - 1 do_CityList[i].Free;_CityList.Clear();
end;constructor TProvince.Create;
begin_CityList := Tlist<TCity>.Create();
end;destructor TProvince.Destroy;
beginclear_CityList();FreeAndNil(_CityList);inherited;
end;{ TCity }procedure TCity.clear_CountyList;
vari: Integer;
beginfor i := 0 to _CountyList.Count - 1 do_CountyList[i].Free;_CountyList.Clear();
end;constructor TCity.Create;
begin_CountyList := Tlist<TCounty>.Create();
end;destructor TCity.Destroy;
beginclear_CountyList();FreeAndNil(_CountyList);inherited;
end;{ TCounty }constructor TCounty.Create;
begin//
end;destructor TCounty.Destroy;
begininherited;
end;{ TStation }constructor TStation.Create;
begin//
end;destructor TStation.Destroy;
begininherited;
end;{ TStation_Path }constructor TStation_Path.Create;
begin//
end;destructor TStation_Path.Destroy;
begininherited;
end;{ TStation_Path_Node }procedure TStation_Path_Node.add_next(next_node: TStation_Path_Node;Mileage: Integer);
varn: TStation_Next;
beginn := TStation_Next.Create;n.Station_Node_Next := next_node;n.Mileage := Mileage;_Next_Station.Add(n);
end;procedure TStation_Path_Node.add_Prior(p_node: TStation_Path_Node;Mileage: Integer);
varn: TStation_Next;
beginn := TStation_Next.Create;n.Station_Node_Next := p_node;n.Mileage := Mileage;_Prior_Station.Add(n);
end;procedure TStation_Path_Node.clear_Next_Station;
vari: Integer;
beginfor i := 0 to _Next_Station.Count - 1 do_Next_Station[i].Free;_Next_Station.Clear;
end;procedure TStation_Path_Node.clear_Prior_Station;
vari: Integer;
beginfor i := 0 to _Prior_Station.Count - 1 do_Prior_Station[i].Free;_Prior_Station.Clear;
end;constructor TStation_Path_Node.Create;
begin_path_mileage := 0;_is_on_path := false;_step := -1;_Next_Station := Tlist<TStation_Next>.Create();_Prior_Station := Tlist<TStation_Next>.Create();
end;destructor TStation_Path_Node.Destroy;
beginclear_Next_Station();FreeAndNil(_Next_Station);clear_Prior_Station();FreeAndNil(_Prior_Station);inherited;
end;procedure TStation_Path_Node.reset;
begin_is_on_path := false;_is_end := false;_step := -1;_is_before_end := false;_path_mileage := 0;_Path_Prior_Station := nil;
end;procedure TStation_Path_Node.set_is_before_end;
vari: Integer;
begin_is_end := True;for i := 0 to _Prior_Station.Count - 1 dobeginif (_Prior_Station[i].Station_Node_Next.is_before_end) thenif _Prior_Station[i].Station_Node_Next._to_end_mileage < _Prior_Station[i]._Mileage thenContinue;_Prior_Station[i].Station_Node_Next._is_before_end := True;_Prior_Station[i].Station_Node_Next._end_Node := self;_Prior_Station[i].Station_Node_Next._to_end_mileage :=_Prior_Station[i]._Mileage;end;
end;procedure TStation_Path_Node.set_Step(v: Integer);
begin_step := v;_is_on_path := True;
end;{ TStation_Next }constructor TStation_Next.Create;
begin//
end;destructor TStation_Next.Destroy;
begininherited;
end;{ TR_Path }constructor TR_Path.Create;
beginStationList := Tlist<TStation>.Create();
end;destructor TR_Path.Destroy;
beginFreeAndNil(StationList);inherited;
end;function TR_Path.get_txt: string;
vari: Integer;
beginResult := '';for i := 0 to StationList.Count - 1 dobeginif i > 0 thenResult := Result + ' -> ';Result := Result + StationList[i].Name;end;Result := Result + ' (' + IntToStr(Mileage) + ')'
end;function TR_Path.get_txt_with_city: string;
vari: Integer;
beginResult := '';for i := 0 to StationList.Count - 1 dobeginif i > 0 thenResult := Result + '>';Result := Result + StationList[i].CityID.ToString() + '|' +StationList[i].Name;end;Result := Result + ':' + IntToStr(Mileage)
end;end.

应用背景

全国的长途车车站的数据的更新：

同城转车的处理

使用发车班次时间表进行总时长的计算

代码实现

初始化

寻路

操作说明

全部代码

相关文章：