Дейкстры Алгоритм: неверный путь

Question

Когда я вычислить пути снова вершины C to M

Правильный путь должен быть

C -> B -> N -> M 

Но

A -> B -> N -> M 

Я использовал этот код Dijkstra Algorithm

Это изображение для моего графика:

Answer 1

Это потому, что вы первый вызов функция вычисление для А затем вызвать его для C. некоторых полей, как это:

public double minDistance = Double.POSITIVE_INFINITY; 
public Vertex previous; 

уже имеет значение, так что вам нужно удалить pathcomputation для A или очистить эти значения, вы можете сделать это с помощью функции, как:

public void clear() { 
    minDistance = Double.POSITIVE_INFINITY; 
    previous = null; 
} 

внутри этого Vertex класса, и называют это так:

for (Vertex v : vertices) { 
    v.clear(); 
} 

перед тем computePaths(v2);

here является онлайн-версию вашего кода, вы можете увидеть, что выход:

Distance to B: 1.0 
Path: [A, B] 
Distance to M: 5.0 
Path: [C, B, N, M]