Qual é a melhor estrutura de dados padrão para construir um gráfico?

Podes definir uma estrutura Edge Como

struct Edge
{
    int destination;
    int weight;
};

E criar um gráfico como

vector<vector<Edge> > graph;

Então para acessar todas as arestas que vêm do vértice u, você escreve algo como

for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    // here edge.destination and edge.weight give you some details.
}

Pode-se adicionar dinamicamente novas arestas, por exemplo uma aresta do 3º vértice ao 7º com um peso de 8:

Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

Etc.

Para grafos não direcionados não deve esquecer-se de adicionar a aresta simétrica, é claro.

Editar Escolha dos contentores de base(std::vector, std::list, std::map) depende do caso de uso, por exemplo, o que você está fazendo com o grafo mais frequentemente: Adicionar/Remover vértices/arestas, apenas atravessando. Uma vez que seu grafo é criado, std::list ou std::vector é igualmente bom para Dijkstra, std::vector sendo um pouco mais rápido graças ao padrão de acesso sequencial do estágio de relaxamento.

Um grafo que contém Nós cada nó tem id e lista de arestas cada aresta tem o outro nó id e a distância

Se considerarmos cada identificador de nó como um índice. Podemos desenhar uma matriz nxn das bordas da seguinte forma.

Isto pode ajudá-lo a desenhar o gráfico com as arestas.

     [0][1][2][3]

[0] | 1  0  0  0|
[1] | 0  0  1  0|
[2] | 1  0  0  1|
[3] | 0  0  1  0|

Então, uma matriz 2D é uma boa representação da matriz.

int maxtrix[4][4] = new int[4][4];