Ir ao conteúdo
  • Cadastre-se

Eltonsdm

Membro Júnior
  • Posts

    5
  • Cadastrado em

  • Última visita

Reputação

0
  1. Estou implementando um algoritmo de dijkstra para grafo porém o peso das arestas muda com o tempo, como posso implementar isso?
  2. Ja consegui resolver esse problema, mas aproveitando eu implementei o algoritmo de Dijkstra e está funcionando corretamente mas não consigo encontrar os vértices pelo qual ele passa somente o custo. segue o algoritmo public class Dijkstra { final static int INF = 10000; public static int dijkstra(Graph grafo, int origem, int destino){ int numVertices = grafo.numVertices (); int dist[] = new int[numVertices]; int vis[] = new int[numVertices]; int parent[] = new int[numVertices]; for (int v = 0; v < numVertices; v++){ dist[v] = INF; vis[v] = 0; } dist[origem] = 0; int v = origem;//menor atual while(vis[v] == 0){ //atualiza os vizios de V Celula ptr = (Celula) grafo.adj[v].primeiro(); while(ptr != null){ int w = ptr.vertice(); int peso = ptr.peso(); relax(v, w, peso, dist); ptr = (Celula) grafo.adj[v].proximo(); } vis[v] = 1; //marca como visitado int w, min_dist = INF; //achar o vertice w de G que contem a menor distancia //mas que ainda nao foi processado (vis[w] = 0) for(w = 0; w < numVertices; w++){ if(vis[w] == 0 && dist[w] < min_dist){ v = w; min_dist = dist[w]; parent[w] = v; } } } return dist[destino]; } public static void relax(int v, int w, int peso, int[] dist) { if(dist[v] + peso < dist[w] ){ dist[w] = dist[v] + peso; } } }
  3. Quando tento inserir uma segunda aresta no meu grafo da erro "Exception in thread "main" java.lang.NullPointerException"; segue em anexo o código completo. por aqui vou mandar somente a main. package guiadomochileiro.Principal; import guiadomochileiro.Graph.Graph; import java.util.Scanner; public class Principal { public static void main(String[] args) { Scanner ler = new Scanner(System.in); int v1,v2,numArestas,numVertices; float peso; System.out.println("Digite o numero de Vertices Arestas: "); numVertices = ler.nextInt(); numArestas = ler.nextInt(); Graph grafo = new Graph(numVertices); for(int i = 0; i<numArestas; i++){ v1 = ler.nextInt(); v2 = ler.nextInt(); peso = ler.nextFloat(); grafo.insereAresta(v1, v2, peso); } grafo.imprime(); } } GuiaDoMochileiro.rar

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...