mysql - 如何高效地存储位置和路径并找出最短的旅行路线

Question

我在解决面试问题时卡住了。

         place C

place A----------Place B


      place D

假设我可以通过 3-4 条路径从地点 A 到达地点 B(直接路径和间接路径)。

我必须存储它们并检索最短路径。

我可以做表格，但我无法选择最短距离路径。

我创建了如下表格。

table1:
create LocationDetails(
  locnid integer primary key,
  locnname text
  );

table 2:
create PathDescription(
  pathid integer primary key,
  startlocnid integer,
  endlocnid integer,
  distance integer
  );

ALTER TABLE PathDescription
  ADD CONSTRAINT fk_PathDescription1
  FOREIGN KEY (startlocnid)
  REFERENCES Persons(locnid);

ALTER TABLE PathDescription
  ADD CONSTRAINT fk_PathDescription
  FOREIGN KEY (endlocnid)
  REFERENCES Persons(locnid);

但是现在的问题是选择一条覆盖最小距离的路径作为 从地点 A 到地点 B 有很多间接路径。

请帮帮我

谢谢 问候

Answer 1

要选择最短路径，您应该使用 Dijkstra 算法，您会在 google 上找到很多信息和实现。

在维基百科中还有一个伪代码片段:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm