Применение мемоизации к сумме вершин в графе

Question

Справочная информация. В классе, который я беру, у меня было следующее задание: учитывая пустую карту пар <вершина, целое число> и ориентированный граф, сохраняйте на карте каждую из вершин графа вместе с соответствующей суммойвсех вершин, которые могут быть достигнуты оттуда.Я выполнил задание рекурсивно.Однако я подумал об использовании Memoization для улучшения алгоритма.

Вопрос: Как я могу использовать Memoization для улучшения этого алгоритма?Стоит ли это делать?

Моя проблема в том, что я не вижу, как это можно сделать, поскольку каждая вершина имеет свой набор вершин, связанный с ней.Я попытался создать карту, которая содержит Edge между 2 вершинами и его значением, но как только я попал в foreach внутри sumRec (), я просто не знал, как на самом деле реализовать его.(Я прокомментировал код, связанный с этой попыткой, чтобы вы могли увидеть, что я пытался. Эти комментарии начинаются с @Attempt, поэтому вы сможете быстро их обнаружить)

Код:

ПосколькуМне не разрешено загружать ни библиотеку классов, ни код, который я отправил, я сделал быстрый порт для всего, что необходимо для репликации проблемы.

Класс вершины:

import java.util.ArrayList;
import java.util.List;

public class Vertex {

    public int value;
    public String name;
    public List<Edge> edges;

    public Vertex(String name, int value) {

        this.value = value;
        this.name = name;
        edges = new ArrayList<Edge>();
    }

    public void addEdge(Edge e) {

        this.edges.add(e);
    }

    public boolean equals(Object o) {

        if(o instanceof Vertex) {

            Vertex v = (Vertex) o;
            return v.name.equals(this.name) && (v.value == this.value);
        }

        return false;
    }

    public String toString() {

        return "(" + this.name + " := " + this.value + ")";
    }

}

EdgeКласс:

public class Edge {

    public Vertex start;
    public Vertex end;

    public Edge(Vertex start, Vertex end) {

        this.start = start;
        this.end   = end;
    }

    public String toString() {

        return start.toString() + "-->" + end.toString();
    }
}

DirectedGraph Класс:

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class DirectedGraph {

    public List<Vertex> vertices;

    public DirectedGraph() {

        this.vertices = new ArrayList<Vertex>();
    }

    public List<Vertex> getVertices() {

        return this.vertices;
    }

    public void addVertex(Vertex v) {

        this.vertices.add(v);
    }

}

Основной класс (где у меня есть main () и мой алгоритм. Показан на примере)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import lib.DirectedGraph;
import lib.Edge;
import lib.Vertex;

public class Main {
    // @Attempt
    //static Map<Edge, Integer> memoization;

    public static int sumRec(Vertex v, List<Vertex> visited) {

        if(visited.contains(v)) 
            return 0;

        int sum = v.value;
        List<Edge> edges = v.edges;
        visited.add(v);
        // @Attempt I got stuck here 
        for(Edge e : edges) {

            sum += sumRec(e.end, visited);
        }

        return sum;
    }

    public static Map<Vertex, Integer> sumVertices(DirectedGraph g) {

        Map<Vertex, Integer> sumMap = new HashMap<Vertex, Integer>();
        List<Vertex> vertices = g.getVertices();

        for(Vertex v : vertices) {

            List<Vertex> visited = new ArrayList<Vertex>();
            int sum = sumRec(v, visited);
            sumMap.put(v, new Integer(sum));            
        }

        return sumMap;
    }

    public static void main(String args[]) {

        // @Attempt
        // memoization = new HashMap<Edge, Integer>(); 
        //   /<--------------\
        //  v1 -> v2 -> v3 -> v4
        //  \ v5
        // (Result doesn't need to be in any specific order)
        // Expected: {<v1, 15>, <v2, 15>, <v3, 15>, <v4, 15>, <v5, 5>}
        // Result:{(v1 := 1)=15, (v4 := 4)=15, (v5 := 5)=5, (v3 := 3)=15, (v2 := 2)=15}
        Vertex v1 = new Vertex("v1", 1);
        Vertex v2 = new Vertex("v2", 2);
        Vertex v3 = new Vertex("v3", 3);
        Vertex v4 = new Vertex("v4", 4);
        Vertex v5 = new Vertex("v5", 5);

        Edge e1 = new Edge(v1, v2);
        Edge e2 = new Edge(v2, v3);
        Edge e3 = new Edge(v3, v4);
        Edge e4 = new Edge(v1, v5);
        Edge e5 = new Edge(v4, v1);

        v1.addEdge(e1);
        v1.addEdge(e4);
        v2.addEdge(e2);
        v3.addEdge(e3);
        v4.addEdge(e5);

        DirectedGraph g = new DirectedGraph();

        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);

        System.out.println(sumVertices(g));

    }

}

Спасибо.