fork download
copy 
  1. import java.util.Arrays;
  2.  
  3. public class Main {
  4.     private static final int INFINITY = Integer.MAX_VALUE;
  5.  
  6.     public static void dijkstra(int[][] graph, int startVertex) {
  7.         int numVertices = graph.length;
  8.         int[] distances = new int[numVertices];
  9.         boolean[] visited = new boolean[numVertices];
  10.  
  11.         Arrays.fill(distances, INFINITY);
  12.         distances[startVertex] = 0;
  13.  
  14.         for (int i = 0; i < numVertices - 1; i++) {
  15.             int currentVertex = findMinDistance(distances, visited);
  16.             visited[currentVertex] = true;
  17.  
  18.             for (int j = 0; j < numVertices; j++) {
  19.                 if (!visited[j] && graph[currentVertex][j] != 0 && distances[currentVertex] != INFINITY
  20.                         && distances[currentVertex] + graph[currentVertex][j] < distances[j]) {
  21.                     distances[j] = distances[currentVertex] + graph[currentVertex][j];
  22.                 }
  23.             }
  24.         }
  25.  
  26.         System.out.println("Najkrótsza ścieżka od wierzchołka " + startVertex + " do pozostałych wierzchołków:");
  27.         for (int i = 0; i < numVertices; i++) {
  28.             System.out.println("Do wierzchołka " + i + ": " + distances[i]);
  29.         }
  30.     }
  31.  
  32.     private static int findMinDistance(int[] distances, boolean[] visited) {
  33.         int minDistance = INFINITY;
  34.         int minVertex = -1;
  35.  
  36.         for (int i = 0; i < distances.length; i++) {
  37.             if (!visited[i] && distances[i] < minDistance) {
  38.                 minDistance = distances[i];
  39.                 minVertex = i;
  40.             }
  41.         }
  42.  
  43.         return minVertex;
  44.     }
  45.  
  46.     public static void main(String[] args) {
  47.         int[][] graph = {
  48.                 { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
  49.                 { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
  50.                 { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
  51.                 { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
  52.         };
  53.  
  54.         int startVertex = 0;
  55.         dijkstra(graph, startVertex);
  56.     }
  57. }
  58.  
Success #stdin #stdout 0.15s 50528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Najkrótsza ścieżka od wierzchołka 0 do pozostałych wierzchołków:
Do wierzchołka 0: 0
Do wierzchołka 1: 4
Do wierzchołka 2: 12
Do wierzchołka 3: 19
https://ideone.com/sPfs9l
language:
Java (12.0.1)
created:
326 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!