0

这是班加罗尔地铁地图。

班加罗尔地铁路线

现在我正在设计一个应用程序，它应该告诉用户源和目的地之间的停靠点数。现在假设用户只需要从蓝线中的一个站点到蓝线中的另一个站点。就像这张图一样。。

从 BlueLine 到 BlueLine 的旅行

现在我们可以看到它应该说登机点是 1，目的地是 2，中间有 6 个站点。如何计算中间的停靠点数以及距离。如果线路发生变化，即用户想要从 BlueLine 行驶到 YellowLine，该怎么办。

我有每行的字符串数组形式的停靠点名称.. 这是数组..

 String[] greenline = {"Bangalore International Exhibition Center", "Jindal", "Manjunathnagar", "Nagasandra", "Dasarahalli", "Jalahalli", "Peenya Industry", "Peenya", "Yeswanthpur Industry", "Yeswanthpur", "Sandal Soap Factory", "Mahalaxmi", "Rajajinagar", "Kuvempu Road", "Srirampura", "Sampige Road", "Kempegowda Interchange", "Chikpet", "K R Market", "National College", "Lalbagh", "South End Circle", "Jayanagar", "R V Road Interchange", "Banashankari", "J P Nagar", "Puttenahalli", "Anjanapura Cross Road", "Krishna Leela Park", "Vajrahalli", "Thaighattapura", "Anjanapura/NICE Junction"};

String[] blueline = {"Kengeri", "R V College of Engineering", "Bangalore University Cross", "Rajarajeshwari Nagar", "Nayandahalli", "Mysore Road", "Deepanjali Nagar", "Attiguppe", "Vijayanagar", "Hosahall1i", "Magadi Road", "City Railway Station", "Kempegowda Interchange", "Sir M Vishweshwariah", "Vidhana Soudha", "Cubbon Park", "M G Road Interchange", "Trinity", "Halasuru", "Indiranagar", "S V Road", "Baiyyappanahalli", "Jyotipura", "K R Puram", "Mahadevpura", "Garudacharpalya", "Doddanekkundi Induatrial State", "Vishweshwariah Industrial State", "Kundanahalli", "Vydhehi Hospital", "Satya Sai Medical Institute", "ITPB", "Kadugodi Industrial Area", "Ujjwal Vidhyalaya", "Whitefield"};

String[] redline = {"Nagawara", "Arabic College", "Venkateshpura", "Tannery Town", "Pottery Town", "Cantonment Railway Station", "Shivajinagar", "M G Road Interchange", "Vellara Junction", "Langford Town", "Mico Bosch", "Dairy Circle", "Swagath Road Cross", "Jayadeva Hospital Interchange", "J P Nagar 4th Phase", "IIMB", "Hulimavu", "Gottigere"};

String[] yellowline = {"R V Road Interchange", "Ragigudda Temple", "Jayadeva hospital Interchange", "BTM Layout", "Silk Board", "HSR Layout", "Oxford College", "Muneshwara Nagar", "Chikkabegur", "Basapura Road", "Hosa Road", "Electronics City 1", "Electronics City 2", "Huskur Road", "Hebbagodi", "Bommasandra"};

有人请帮忙。提前谢谢。

4

1 回答 1

2

首先将线列表转换为您将要搜索的图表。

  • 让每个节点保存其名称、边列表及其与源的距离（最初为无穷大）以及最佳路径中的前一个节点

  • 让每条边都包含两个节点，它所属的线及其成本。

  • 准备一个字符串到节点的哈希映射，称为“节点”

  • 准备一组节点，称为“传输节点”。您可以为此使用哈希映射字符串 (name) => 节点。
  • 对于每一行：
    • 如果“nodes”没有线路的第一个站点的条目，则创建一个新节点并将其添加到“nodes”。
    • 对于除第一个站外的每个站：
      • 如果“nodes”没有该站的条目，则创建一个新节点并将其添加到“nodes”。
      • 创建一个新的边连接这个站和前一个站。它的代价是团结。
      • 将此边添加到两个站点的边列表中
      • 如果任一节点现在属于多条线路（查找成功），则将此站添加到“传输节点”。

（注意：由于您的行存储在一组变量中，您可以按如下方式执行“每一行”：）

private HashMap<Node> nodes;
private void addLine (String[] stops, String name){...};
// ... ( ... ){ ...
addLine(greenline, "green line");
addLine(blueline,  "blue line" );
//...

如果转移成本不为零，则添加转移成本：

  • 对于“传输节点”中的每个节点：
    • 对于使用该节点的每一行：
      • 创建一个新节点，以原始节点命名。
      • 将该行的所有（一个或两个）边重定向到新节点 - 更改它们的源或目标并将它们添加到新节点边列表中。
    • 对于每对新站节点
      • 创建一条连接它们的新边，并将这条边添加到两个节点的边列表中。它的成本是转移成本。

现在，找到从源到目的地的最便宜的路径。我将展示 Dijkstra 算法：

  • 准备一个节点优先级队列，称为“开放集”。如果传输成本为零或一，您可以为此使用普通队列。
  • 将源节点添加到“开放集”。如果起始站是中转站，则将所有关联节点添加到“开放集”中。
  • 将源节点与源的距离设置为零
  • 重复
    • 从“open set”中弹出一个名为“from”的节点。如果不存在这样的元素，则为错误。如果节点对应于目标站，则中断循环，记住“来自”。
    • 对于该节点的每个邻居，称为“to”：
      • 计算“到”的新距离。它是“从”的距离加上连接边的长度
      • 如果新距离比“to”的当前距离短：
        • 更新“到”的距离。
        • 将“to”的前沿更新为“from”和“to”之间的边缘。
        • 如果距离是无穷大，将“to”添加到“open set”
        • 否则更新“开放集”中“到”的位置
  • 沿最佳路径收集边缘：
  • 从一个空的边列表开始
  • 让当前节点为“来自”。
  • 而当前节点定义了前一条边：
    • 否则将前一条边添加到边列表中
    • 让当前节点成为这条边上的另一个节点

现在剩下的就是读取路径：

  • 将边沿计数器初始化为 1
  • 对于边列表中的每条边：
    • 如果这是第一条边，则输出“从旅行edge.line开始start”。
    • 否则，如果前一个边沿是转移边沿，则输出“在count停止后，转移到edge.line”prevEdge.node[0].name并重置边沿计数器。
    • 否则增加边缘计数器。
  • 输出“%count停止后，退出%target”。
于 2013-10-11T08:27:12.770 回答