Bellman-Ford Implementation in Scala/Java

I think the part to get shortest path from the cost table got pretty messy. Also can use some tips on how to avoid the extra O(V+E) work checking all edges from source to dest after getting the cost table, or have a better optimized implementation in general.

DirectedGraph.scala

case class Vertex(id: String)
case class Edge(source: Vertex, dest: Vertex, weight: Int)


class DirectedGraph {
  val adjacencyTable: mutable.Map[Vertex, Array[Edge]] = new mutable.HashMap[Vertex, Array[Edge]]()

  def addVertex(vertex: Vertex): Unit = adjacencyTable.put(vertex, new Array[Edge](0))

  def addEdge(source: Vertex, dest: Vertex, weight: Int): Unit =
    adjacencyTable.put(source, adjacencyTable(source) :+ Edge(source, dest, weight))

  def getEdges: Array[Edge] = adjacencyTable.keys.flatMap(i => adjacencyTable(i)).toArray
}

BellmanFord.java

public class BellmanFord {

  private DirectedGraph graph;

  public BellmanFord(DirectedGraph graph) {
    this.graph = graph;
  }

  public List<Vertex> getShortestPath(Vertex source, Vertex dest) {
    Map<Vertex, Integer> costs = getCostMap(source);
    List<Vertex> retList = new ArrayList<>();
    Edge minEdge = null;
    
    retList.add(source);

    if (source == dest) return retList;
    if (graphHasNegativeCycle(costs))
      throw new IllegalStateException("Graph cannot have negative cycles");
    if (costs.get(dest) == Integer.MAX_VALUE)
      throw new IllegalArgumentException("There are no valid paths from source to destination");
    
    for (Edge e : graph.adjacencyTable().get(source).get())
      if (minEdge == null || e.weight() < minEdge.weight())
        minEdge = e;

    retList.addAll(getShortestPath(minEdge.dest(),dest));
    return retList;
  }

  private Map<Vertex, Integer> getCostMap(Vertex source) {
    Map<Vertex, Integer> ret = initCostMap(source);
    for (int i = 0; i < ret.size() - 1; i++) {
      relaxEdges(ret);
    }
    return ret;
  }

  private void relaxEdges(Map<Vertex, Integer> costMap) {
    for (Edge edge : graph.getEdges()) {
      if (costMap.get(edge.source()) + edge.weight() < costMap.get(edge.dest())) {
        costMap.put(edge.dest(), costMap.get(edge.source()) + edge.weight());
      }
    }
  }
  
  private boolean graphHasNegativeCycle(Map<Vertex, Integer> costMap) {
    for (Edge edge : graph.getEdges()) {
      if (costMap.get(edge.source()) + edge.weight() < costMap.get(edge.dest())) {
        return true;
      }
    }
    return false;
  }

  private Map<Vertex, Integer> initCostMap(Vertex source) {
    Map<Vertex, Integer> costMap = new HashMap<>();
    graph.adjacencyTable().foreach(
        kvp -> costMap.put(kvp._1, kvp._1 == source ? 0 : Integer.MAX_VALUE)
    );
    return costMap;
  }
}