Java - Ayuda problema de grafos

Considere el mapa de Colombia como un grafo, es decir cada ciudad dentro del mapa es un
vértice y el camino que une a las ciudades son las aristas, por ejemplo:
Represente a través de una matriz de adyacencia el grafo que usted de manera independiente
desea construir, es decir, usted define las ciudades y los posibles caminos entre las ciudades (No
puede existir un grafo igual, asegúrese que ningún compañero o compañera tenga el mismo
grafo).
Construya un programa en java que lea la matriz de adyacencia y pueda hacer el computo para
encontrar es el camino mas corto entre dos ciudades.