fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static final int INF = Integer.MAX_VALUE;
  5.  
  6.     public static int shortestPath(int[][] graph, int n) {
  7.         int[] cost = new int[n];
  8.         int[] path = new int[n];
  9.  
  10.         cost[n - 1] = 0;
  11.  
  12.         for (int i = n - 2; i >= 0; i--) {
  13.             cost[i] = INF;
  14.             for (int j = i + 1; j < n; j++) {
  15.                 if (graph[i][j] != 0 && cost[i] > graph[i][j] + cost[j]) {
  16.                     cost[i] = graph[i][j] + cost[j];
  17.                     path[i] = j;
  18.                 }
  19.             }
  20.         }
  21.  
  22.         System.out.print("Shortest Path: ");
  23.         int i = 0;
  24.         while (i != n - 1) {
  25.             System.out.print(i + " -> ");
  26.             i = path[i];
  27.         }
  28.         System.out.println(n - 1);
  29.  
  30.         return cost[0];
  31.     }
  32.  
  33.     public static void main(String[] args) {
  34.         int[][] graph = {
  35.             // 0  1  2  3  4  5  6  7
  36.             { 0, 1, 2, 5, 0, 0, 0, 0 }, // 0
  37.             { 0, 0, 0, 0, 4, 11, 0, 0 }, // 1
  38.             { 0, 0, 0, 0, 9, 5, 16, 0 }, // 2
  39.             { 0, 0, 0, 0, 0, 0, 2, 0 }, // 3
  40.             { 0, 0, 0, 0, 0, 0, 0, 18 }, // 4
  41.             { 0, 0, 0, 0, 0, 0, 0, 13 }, // 5
  42.             { 0, 0, 0, 0, 0, 0, 0, 2 },  // 6
  43.             { 0, 0, 0, 0, 0, 0, 0, 0 }   // 7 (destination)
  44.         };
  45.  
  46.         int n = graph.length;
  47.         int cost = shortestPath(graph, n);
  48.         System.out.println("Minimum Cost: " + cost);
  49.     }
  50. }
  51.  
Success #stdin #stdout 0.17s 55396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Shortest Path: 0 -> 3 -> 6 -> 7
Minimum Cost: 9
https://ideone.com/jZ5pJv
language:
Java (HotSpot 12)
created:
1 day 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!