-1

我正在尝试实现一个室内导航系统，我必须找到从我当前位置到某个点的最短路径。

我已经达到的目标：使用 Dijkstra 的算法/Hipster 和一个测试代码，我在其中定义了 4 个具有权重的节点，然后尝试找到从源到目的地的最短路径。

现在的情况是，如果假设我在地图上的一个未定义为节点的点，并且我想导航到一个可能是也可能不是节点的点，那么在这种情况下如何找到最短路径？

我正在使用的当前测试代码：

package indoornav.shortestpath;

import java.util.List;

import es.usc.citius.hipster.algorithm.Hipster;
import es.usc.citius.hipster.graph.GraphBuilder;
import es.usc.citius.hipster.graph.GraphSearchProblem;
import es.usc.citius.hipster.graph.HipsterDirectedGraph;
import es.usc.citius.hipster.model.problem.SearchProblem;

public class Client3 {
    public static void main(String[] args)
    {
        HipsterDirectedGraph<String,Double> graph = 
                GraphBuilder.<String,Double>create()
                 .connect("A").to("D").withEdge(10d)
                 .connect("A").to("C").withEdge(12d)
                 .connect("C").to("A").withEdge(12d)
                 .connect("C").to("B").withEdge(10d)
                 .connect("B").to("D").withEdge(10d)
                 .connect("B").to("C").withEdge(10d)
                 .connect("D").to("A").withEdge(10d)
                 .connect("D").to("B").withEdge(10d)

                 .createDirectedGraph();

            // Create the search problem. For graph problems, just use
            // the GraphSearchProblem util class to generate the problem with ease.
            SearchProblem p = GraphSearchProblem
                                       .startingFrom("A")
                                       .in(graph)
                                       .takeCostsFromEdges()
                                       .build();

            // Search the shortest path from "A" to "F"
            System.out.println(Hipster.createDijkstra(p).search("B"));
    }
}

    enter code here
4

1 回答 1

0

我认为您可以找到您所在位置和您需要所在位置的两个相邻节点之间的最短路径。然后需要添加从您的真实位置到起始节点以及从目标位置到目标节点的路径：

A` - real location
A  - start node(neighbor for A`)
B` - target location
B  - target node(neighbor for B`)

result = shortest(A,B) + (A`-A) + (B`-B)
于 2016-08-12T09:31:48.747 回答