algorithm - 用于查找图中最短路径的启发式算法。请批评/改进我的伪代码

Question

我必须实现下面描述的两种启发式算法。两种算法都尝试使用启发式方法找到从给定输入节点到节点 Z 的最短路径。在最短路径中，一个节点最多出现一次(即一个节点不能在最短路径中出现两次或更多次，但允许回溯)。请注意，这两种启发式算法并不总是必须找到正确的最短路径。

两种算法都应从给定的输入节点开始，并迭代地确定最短路径中的下一个节点。在确定选择哪个节点作为下一个节点时，他们使用不同的启发式方法。

令w(n, v)为节点n和节点v之间的边的权重。令dd(v)为从v到目标节点Z的直接距离。

从当前节点n中选择下一个节点时:

算法1:在与节点n相邻的所有节点v中，选择dd(v)最小的节点。

算法 2:在与节点 n 相邻的所有节点 v 中，选择 w(n, v) + dd(v) 最小的节点。

Z 可被所有节点访问。所有的边权重都是正整数。

我已经正确加载了图表，但在实现算法时遇到了问题，所以我放弃了一切，重新开始设计。

这是我的伪代码，如果我遗漏了任何案例或者还有其他我需要考虑的事情，请告诉我。效率很好，但在这种情况下不是必需的。任何提示都有帮助!

//----------    PSEUDOCODE ALGORITHM ONE   ----------//

    /*
    while currentNode != destination:
        add currentNode to visited list and set --> list to track total path, set to track shortest path
        for each node adjacent to currentNode:
            if adjacentNode has minimum direct distance to destination:
                get the connecting edge
                nextNode = adjacentNode --> nextNode = graph.opposite(currentNode, edgeToAdjacentNode)
                if nextNode is not in visited: --> list or set?
                    add edgeWeight to total distance traveled
                    add edgeWeight to shortest path distance
                    add nextNode to visited list and set
                    return find adjacentNode with minimum direct distance to destination (recurse on nextNode?)
                else (nextNode has already been visited, we are backtracking):
                    get the connecting edge from currentNode to nextNode
                    add edgeWeight to total distance traveled
                    remove the edge connecting adjacentNode to nextNode --> so we can't go back
                    remove key of nextNode from direct distance data structure --> so it's no longer shortest
                    return find adjacentNode with minimum direct distance to destination (recurse on currentNode?)
    */

    //----------    END PSUEDOCODE ALGORITHM ONE    ----------//

    //----------    PSEUDOCODE ALGORITHM TWO    ----------//

    /*
    while currentNode != destination:
        add currentNode to visited list and set --> list to track total path, set to track shortest path
        for each node adjacent to currentNode:
            calculate the sum of edgeWeight and direct distance to destination
        nextNode = adjacentNode with minimum sum
        if nextNode is not in visited (list or set?):
            add edgeWeight to total distance traveled
            add edgeWeight to shortest path distance
            add nextNode to visited list and set
            return recurse on nextNode?
        else:
            get the connecting edge from currentNode to nextNode
            add edgeWeight to total distance traveled
            remove the edge connecting adjacentNode to nextNode --> so we can't go back
            remove key of nextNode from direct distance data structure --> so it's no longer shortest
            return find adjacentNode with minimum direct distance to destination (recurse on currentNode?)
    */

    //----------    END PSUEDOCODE ALGORITHM TWO    ----------//

输出示例:

(A)用户输入节点J作为起始节点

算法一:

所有节点的顺序:J -> K -> Z最短路径:J -> K -> Z最短路径长度:310

算法 2:

所有节点的顺序:J -> I -> L -> Z路径:J -> I -> L -> Z长度:278

(B)用户输入节点G作为起始节点

算法一:

所有节点的顺序:G -> H -> T -> H -> L -> Z最短路径:G -> H -> L -> Z最短路径长度:359

算法 2:

所有节点的顺序:G -> H -> T -> H -> L -> Z最短路径:G -> H -> L -> Z最短路径长度:359

Answer 1

我让他们都工作了。回答我自己的问题以防万一其他人对解决方案感兴趣。如果您想查看我使用的辅助函数或其他数据结构，请告诉我。干杯。

import accessories.*;
import accessories.Map;
import accessories.AdjacencyMapGraph.InnerVertex;

import java.util.*;
import static accessories.HelperFunctions.*;

public class project {

public static void main(String[] args) {

//----------    CREATION OF THE GRAPH AND DIRECT DISTANCE MAP  ----------//
    // create the adjacency matrix
    ArrayList<String[]> edgeList = readFile();
    // create empty graph
    AdjacencyMapGraph<String, Integer> graph = new AdjacencyMapGraph<>(true);

    //----------    UTILITY DATA STRUCTURES ----------//
    ArrayList<Vertex<String>> vertexListOne = new ArrayList<>();
    Set<Vertex<String>> vertexSetOne = new LinkedHashSet<>();
    ArrayList<Vertex<String>> deadEndsOne = new ArrayList<>();
    int shortestPathDistanceOne = 0;
    ArrayList<Vertex<String>> vertexListTwo = new ArrayList<>();
    Set<Vertex<String>> vertexSetTwo = new LinkedHashSet<>();
    ArrayList<Vertex<String>> deadEndsTwo = new ArrayList<>();
    int shortestPathDistanceTwo = 0;


    // load the graph with Vertices and Edges
    graph = loadGraph(graph, edgeList);
    // create a HashMap of Vertices direct distance to destination
    Map<String, Integer> directDistMap = createDirectDistanceMap();


//----------    GET USER INPUT  ----------//
    // get the starting vertex
    Scanner selection = new Scanner(System.in);
    // prompt user
    System.out.println("Enter a node: ");
    String start = selection.nextLine().toUpperCase();

    // the destination Vertex
    Vertex<String> destination = setDestination(graph);

    // currentVertex is the current accessories.Vertex
    Vertex<String> currentVertex = getStartingVertex(graph, start);

    //----------    ALGORITHM ONE   ----------//
    Vertex<String> startVertex = currentVertex;
    while (!startVertex.equals(destination)) {
        // add startVertex to list and set
        vertexListOne.add(startVertex);
        vertexSetOne.add(startVertex);
        // for each adjacentVertex map the direct distance to the destination
        LinkedHashMap<Vertex<String>, Integer> adjVertDirDist = new LinkedHashMap<>();
        for (Edge<Integer> outgoingEdge : graph.outgoingEdges(startVertex)) {
            Vertex<String> adjacentVertex = graph.opposite(startVertex, outgoingEdge);
            if (!deadEndsOne.contains(adjacentVertex)) {
                int dd = directDistMap.get(adjacentVertex.getElement());
                adjVertDirDist.put(adjacentVertex, dd);
            }
        }
        // sort the adjVertDirDist by value and save it in a list
        List<java.util.Map.Entry<Vertex<String>, Integer>> list = sortMapByValue(adjVertDirDist);
        // first entry has vertex with closest direct distance to destination
        Vertex<String> nextVertex = list.get(0).getKey();
        // if nextNode is not in visited
        Edge<Integer> edge = graph.getEdge(startVertex, nextVertex);
        if (!vertexSetOne.contains(nextVertex)) {
            // add edgeWeight to shortestPathTraveled
            shortestPathDistanceOne += edge.getElement();
            startVertex = nextVertex;
            if (startVertex.equals(destination)) {
                // WE MADE IT!
                vertexListOne.add(startVertex);
                vertexSetOne.add(startVertex);
            }
        } else {
            // decrement shortest path distance
            shortestPathDistanceOne -= edge.getElement();
            // remove from set
            vertexSetOne.remove(startVertex);
            // mark dead end
            deadEndsOne.add(startVertex);
            // go to nextVertex (will be previous vertex)
            startVertex = nextVertex;
        }
    }

    displayResults(shortestPathDistanceOne, vertexListOne, vertexSetOne, 1);
    //----------    END ALGORITHM ONE   ----------//

    //----------    ALGORITHM TWO   ----------//

    Vertex<String> startVertexTwo = currentVertex;
    while (!startVertexTwo.equals(destination)) {
        // add startVertexTwo to list and set
        vertexListTwo.add(startVertexTwo);
        vertexSetTwo.add(startVertexTwo);
        // for each adjacentVertex map the direct distance to the destination
        LinkedHashMap<Vertex<String>, Integer> adjVertDirDist = new LinkedHashMap<>();
        for (Edge<Integer> outgoingEdge : graph.outgoingEdges(startVertexTwo)) {
            Vertex<String> adjacentVertex = graph.opposite(startVertexTwo, outgoingEdge);
            if (!deadEndsTwo.contains(adjacentVertex)) {
                int ddPlusWeight = outgoingEdge.getElement() + directDistMap.get(adjacentVertex.getElement());
                adjVertDirDist.put(adjacentVertex, ddPlusWeight);
            }
        }
        // sort the adjVertDirDist by value and save it in a list
        List<java.util.Map.Entry<Vertex<String>, Integer>> list = sortMapByValue(adjVertDirDist);
        // first entry has vertex with closest direct distance to destination
        Vertex<String> nextVertex = list.get(0).getKey();
        // if nextNode is not in visited
        Edge<Integer> edge = graph.getEdge(startVertexTwo, nextVertex);
        if (!vertexSetTwo.contains(nextVertex)) {
            // add edgeWeight to shortestPathTraveled
            shortestPathDistanceTwo += edge.getElement();
            startVertexTwo = nextVertex;
            if (startVertexTwo.equals(destination)) {
                // WE MADE IT!
                vertexListTwo.add(startVertexTwo);
                vertexSetTwo.add(startVertexTwo);
            }
        } else {
            // decrement shortest path distance
            shortestPathDistanceTwo -= edge.getElement();
            // remove from set
            vertexSetTwo.remove(startVertexTwo);
            // mark dead end
            deadEndsTwo.add(startVertexTwo);
            // go to nextVertex (will be previous vertex)
            startVertexTwo = nextVertex;
        }
    }
    System.out.println();
    displayResults(shortestPathDistanceTwo, vertexListTwo, vertexSetTwo, 2);

}   //----------    END MAIN    ----------//