fork download
copy 
  1. /*
  2. Demo graph (example taken from http://p...content-available-to-author-only...t.net/~cazelais/222/dijkstra.pdf): 
  3.  
  4.       b       d
  5.       O-------O
  6.      /|\      |\
  7.    2/ | \3    | \2
  8.    /  |  \   1|  \
  9. a O   |   \   |   O z
  10.    \  |6   \  |  /
  11.    3\ |     \ | /4
  12.      \|      \|/
  13.       O-------O
  14.       c       d
  15. */
  16. class Demo {
  17.     static public void main(String[] args) {
  18.         double[][] _m = {
  19.             {   0,    2,    3, 1000, 1000, 1000},
  20.             {   2,    0,    6,    5,    3, 1000},
  21.             {   3,    6,    0, 1000,    1, 1000},
  22.             {1000,    5, 1000,    0,    1,    2},
  23.             {1000,    3,    1,    1,    0,    4},
  24.             {1000, 1000, 1000,    2,    4,    0}
  25.         };
  26.         int _root = 0;
  27.  
  28.         double mincost, cost[] = new double[_m.length];
  29.         int frj[], parent[], w0;
  30.  
  31.         frj = new int[_m.length];
  32.         parent = new int[_m.length];
  33.  
  34.         for (int w = 0; w < _m.length; w++) {
  35.             parent[w] = -1;
  36.             cost[w] = _m[_root][w];
  37.             frj[w] = _root;
  38.         }
  39.  
  40.         parent[_root] = _root;
  41.         cost[_root] = 0;
  42.         w0 = 0;
  43.  
  44.         while (true) {
  45.             mincost = -1;
  46.  
  47.             for (int w = 0; w < _m.length; w++) {
  48.                 if (parent[w] != -1 || cost[w] == 0) {
  49.                     continue;
  50.                 }
  51.  
  52.                 if (mincost > cost[w] || mincost == -1) {
  53.                     mincost = cost[w0 = w];
  54.                 }
  55.             }
  56.  
  57.             if (mincost == -1) {
  58.                 break;
  59.             }
  60.  
  61.             parent[w0] = frj[w0];
  62.             for (int w = 0; w < _m.length; w++) {
  63.                 if (cost[w] > cost[w0] + _m[w0][w]) {
  64.                     cost[w] = cost[w0] + _m[w0][w];
  65.                     frj[w] = w0;
  66.                 }
  67.             }
  68.         }
  69.  
  70.         for (int i = 0; i < parent.length; i++) {
  71.             System.out.print(" " + parent[i]);
  72.         }
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 0 0 0 4 2 3
https://ideone.com/DmX0EP
Illustration of answer to http://stackoverflow.com/questions/16798961/dijkstra-algorithm-implemented-in-c-and-converted-to-java.
language:
Java (12.0.1)
created:
12 years ago
visibility:
secret

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!