Hint: construct another graph G' so that computing the shortest path from s to t on G' is equivalent with solving the given problem in the original graph G. The new graph G' will include the nodes and edges of G -- but it will also have some additional nodes and edges that we will construct to capture that we can travel between any two nodes of the same label.

Please justify your runtime and include a proof of correctness for your algorithm.

Suppose we are given a connected graph G=(V,E) with V=n,E=m. Each edge eE has a positive weight w(e)>0. Each vertex vV has a label av{1,2,,k}. Each label i{1,2,,k}, has a cost ci. t each vertex uV, you can perform two types of operations: 1. You can travel from u to some vertex v in its neighborhood, i.e. any v such that e=(u,v)E. The cost of this operation is w(e). 2. You can travel from u to some vertex v with the same label, i.e. any v such that au=av. The cost of this operation is cau. Given a source vertex s and a sink vertex t, design an O(X) algorithm that computes the minimal cost of traveling from s to t where O(X) is Dijkstra's shortest path algorithm runtime complexity on a graph with O(n) vertices and O(m) edges