Implement a method to compute the shortest path from source
to target
in
a graph using Djikstra Algorithm.
The method should return a List
of Vertices
denoting the optimal path.
Click "Use Me" to understand the Vertex
and Edge
classes.
Example: V2 | \ |10 \3 | 5 \ 7 V0 ——-- V1 ——— V4 \ / \8 /2 \ / V3 v0 = Rville v1 = Bville v2 = Gville v3 = Oville v4 = Pville Shortest Path to V3 from V0 = [Rville, Oville]
Comparable
.
Write a method to compute the shortest distances among the vertices in the given graph.
Where is the graph? Notice that each vertex
has a set of Edge
es, where each Edge
is pointing to another Vertex
.
So you would need to update:
minDistance
: the minimum distance from previous node to the given vertex
previous
: previous node of the optimal path from source
Here is a pseudocode of one possible problem.solution=
function Dijkstra(Graph, source):
dist[source] := 0
for each vertex v in Graph:
if v ≠ source
dist[v] := infinity
previous[v] := undefined
end if
PQ.add_with_priority(v,dist[v])
end for
while PQ is not empty:
u := PQ.extract_min()
for each neighbor v of u:
alt = dist[u] + length(u, v)
if alt < dist[v]
dist[v] := alt
previous[v] := u
PQ.decrease_priority(v,alt)
end if
end for
end while
return previous[]
public static List<Vertex> getShortestPath(Vertex source, Vertex target) { }
C
Java
Python