Печать кратчайшего пути в матрице смежности

Question

Я создал сеть (ориентированный взвешенный граф), которая содержит матрицу смежности с вершинами и взвешенными ребрами.

У меня настроен класс Path, а также очередь потенциальных путей иDeque возможных решений.Если узел уже был посещен, он помечается как посещенный, в противном случае он добавляется к потенциальным путям, а соседние узлы проверяются.Затем рассчитывается лучший путь на основе веса.

У меня проблемы с возвратом строки кратчайшего пути.Я пытаюсь создать строку из вершин в кратчайшем пути от начала до конца.Однако, когда я тестирую и запускаю getShortestPath, я получаю области памяти, а не значения String.

Вот код для кратчайшего пути:

// get shortest path from a starting vertex to ending vertex

  public String getShortestPath(String origin, String destination)
  {
    origin = origin.toUpperCase();
    destination = destination.toUpperCase();

    for (int i = 0; i < vertices.size(); i++)
    {
      return findShortestPath(origin, destination).toString();
    }
    return "";
  }

  public List<Edge> adjacentEdges(String origin)
  {
    List<Edge> result = new LinkedList<Edge>();

    for (Edge e : edges)
    {
      if (e.origin.name.compareTo(origin) == 0)
        result.add(new Edge(e.origin, e.destination, e.weight));
    }
    return result;
  }

  public Path findShortestPath(String origin, String destination)
  {
    if (origin.compareTo(destination) == 0)
    {
      return null;
    }

    Queue<Path> potentialPaths = new LinkedList<Path>();

    for (Edge e : adjacentEdges(origin))
    {
      Path current = new Path();
      current.edges.add(new Edge(e.origin, e.destination, e.weight));
      potentialPaths.add(current);
      System.out.println(potentialPaths);
    }

    Deque<Path> solutions = new LinkedList<Path>();

    while (!potentialPaths.isEmpty())
    {
      Path current = potentialPaths.remove(); // dequeue
      String[] nodes = current.toString().split("-");
      Edge last = current.edges.getLast();

      if (last.destination.name.compareTo(destination) == 0) // found valid path
      {
        solutions.add(current);
        continue;
      }
      // if not at the destination
      List<Edge> adjacencies = adjacentEdges(last.destination.name);

      for (Edge adj : adjacencies)
      {
        boolean visited = false;

        for (Edge pe : current.edges)
        {
          if (adj.destination.name.compareTo(pe.origin.name) == 0) // already been to this node in the path
          {
            visited = true;
          }
        }

        // if not already visited, add edge to path and enqueue it to potential paths
        if (!visited)
        {
          Path candidate = new Path();

          for (Edge pe : current.edges)
          {
            candidate.edges.add(new Edge(pe.origin, pe.destination, pe.weight));
          }

          candidate.edges.add(new Edge(adj.origin, adj.destination, adj.weight));

          potentialPaths.add(candidate);
        }
      }
    }
    // done going through all potential paths
    // loop through solutions for best weight

    if (solutions.isEmpty())
      return null;

    Path best = solutions.remove();
    double weight = calcWeight(best);

    while (!(solutions.isEmpty()))
    {
      Path current = solutions.remove();
      double currentWeight = calcWeight(current);

      if (currentWeight < weight)
      {
        best = current;
        weight = currentWeight;
      }
    }

    return best;
  }

  public double calcWeight(Path path)
  {
    double weight = 0.0;

    for (Edge e : path.edges)
    {
      weight += e.weight;
    }

    return weight;
  }

  public class Path
  {
    public Deque<Edge> edges;

    public Path()
    {
      edges = new LinkedList<Edge>();
    }
  }

А остальная часть кода моего класса Network,при необходимости:

public class Network
{
  // instance variables

  public List<Vertex> vertices;
  public List<Edge> edges;

  // constructor

  public Network()
  {
    vertices = new LinkedList<Vertex>();
    edges = new LinkedList<Edge>();
  }

  // adjacency matrix

  public class AdjacencyMatrix
  {
    String vertexNames[];
    double matrix[][];

    public AdjacencyMatrix()
    {
      final int size = vertices.size();
      vertexNames = new String[size];
      matrix = new double[size][size];

      int i = 0;
      for (Vertex v : vertices)
      {
        vertexNames[i++] = v.name;
      }


    for (Edge e : edges)
    {
      int row = getIndex(e.origin.name);
      int column = getIndex(e.destination.name);
      matrix[row][column] = e.weight;
    }
  }

   private int getIndex(String name)
    {
     for (int i = 0; i < vertexNames.length; i++)
      {
       if (vertexNames[i].compareTo(name) == 0)
         return i;
       }
     return -1;
     }
  }

  // getAdjacencyMatrix

  public AdjacencyMatrix getAdjacencyMatrix()
  {
    return new AdjacencyMatrix();
  }

 // add vertices 

  public boolean addVertex(String name)
  {
    for (Vertex v : vertices)
    {
      if (v.name.compareTo(name) == 0)
      {
        return false;
      }
    }

      Vertex v = new Vertex(name);
      v.name = name.toUpperCase();
      vertices.add(v);
      return true;
  }

  // add edges

  public boolean addEdge(String origin, String destination, double weight)
  {
    origin = origin.toUpperCase();
    destination = destination.toUpperCase();

    Vertex originVertex = null;

    for (Vertex v : vertices)
    {
      if (v.name.compareTo(origin) == 0)
      {
        originVertex = v;
        break;
      }
    }

    if (originVertex == null)
    {
      return false;
    }

    Vertex destinationVertex = null;

    for (Vertex v : vertices)
    {
      if (v.name.compareTo(destination) == 0)
      {
        destinationVertex = v;
        break;
      }
    }

    if (destinationVertex == null)
    {
      return false;
    }

    for (Edge e : edges)
    {
      if (e.origin == originVertex && e.destination == destinationVertex)
      {
        return false;
      }
    }

    Edge e = new Edge(originVertex, destinationVertex, weight);
    e.origin = originVertex;
    e.destination = destinationVertex;
    e.weight = weight;
    edges.add(e);

    return true;
  }

  // support classes

  public class Vertex<T extends Comparable>
  {
    public String name;

    public List<Edge> edges;

    public Vertex(String name)
    {
      this.name = name;
    }
  }

  public class Edge
  {
    public Vertex origin, destination;
    public double weight;

    public Vertex getSource()
    {
      return origin;
    }

    public Vertex getDestination()
    {
      return destination;
    }

    public int getWeight()
    {
      return (int)weight;
    }

    public Edge(Vertex origin, Vertex destination, double weight)
    {
      this.origin = origin;
      this.destination = destination;
      this.weight = weight;
    }

    public Edge(String origin, String destination, double weight)
    {
      this.origin = new Vertex(origin);
      this.destination = new Vertex(destination);
      this.weight = weight;
    }
  }

  public List<Vertex> getVertices()
  {
    return vertices;
  }

  public List<Edge> getEdges()
  {
    return edges;
  }