Percebi que não é necessário montar o grafo para resolver o problema, basta sabermos as arestas e seus custos. É realmente necessário usar o grafo(no fundo somente usaremos o valor de G->V)?
Muito obrigado.
Guardar todas as arestas e seus custos é simplesmente uma forma diferente de representar o grafo.
Se você conseguir o problema sem usar uma matriz ou lista de adjacência, só guardando as arestas, não tem problema.
Se você conseguir o problema sem usar uma matriz ou lista de adjacência, só guardando as arestas, não tem problema.