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]

Need a **hand?** Try out these hints, one at a time.

You need a data structure that always fetches nodes with the smallest distance. A **PriorityQueue** might be a good option.
For your convenience, the Vertex class is already

`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**