Giudoku Official Site
Dijkstra's Algorithm

The Dijkstra's algorithm is a possible solution for the shortest path problem.
This problem concerns a weighted graph, where all the edges have an assigned "weight", a real number. Given a starting vertex v and an ending vertex u, we want to define (if present) the path from v to u for which the total weight is minimum. The path's weight is easily found by summing up all the weights along the path. Actually, the algorithm only computes this minimum weight, not the actual path, which requires some more programming to be deduced, and graphical libraries to be displayed.
My code will work on a generalization of the shortest path problem: given only a starting vertex, it finds out the minimum necessary weight from that vertex to all the other ones in the graph. It has been demonstrated that the best solution to the shortest path problem in particular is no better than the solution to this more general version.

Let's start with some assumption that will make the problem (and my code) a lot easier. First, all the weights in the graph will be positive numbers; negative values can present a serious issue if circular paths are generated.
Second, for simplicity, I'm using a directed graph; that is, every edge defines a direction from two vertices (from a source to a target) and can't go back unless I define a totally different edge going back the other way.
Third, if no path is present between two vertices, the minimum weight is set to the Java constant Double.POSITIVE_INFINITY.

Let's proceeed with a brief explanation of the algorithm. This is quite complex, so if you don't know the basis, I recommend you find some more precise article.
An important property is that the shortest path problem has an optimal substructure: a subpath of a shortest path is a shortest path too.
Plus, let's call s the starting vertex and d[v] the distance of some generic vertex v from s. The distance is the minimum weight from s to v.

The algorithm starts by initializing some data structures. A priority queue Q (the Vector in my code) is filled with all the vertices. Their initial distances is 0 for s (of course) and +infinity for the other ones.
The general definition uses a set S, at first empty, then filled with the vertices. I don't really need that, but I use an array to store the distances for each vertex: this is because the entries in the priority queue will be removed as the algorithm proceeds, so I need a place to save my results. The vertex number is used as an index in the array.
While the priority queue isn't empty, the minimum vertex u is extracted, the vertex with the minimum distance so far. Then a list of all the vertices that can be reached from u is obtained (adjacency list).
For each element v in the adjacency list, an operation called "relaxation" is performed. First, a note: if v had no ingoing edge, it wouldn't be within reach, therefore its distance will never be updated and will stay infinity until the end of the loop.
If I can reach v, I can take a certain number of ways: the way coming from u, with a weight of d[u] + w(u,v), and other ways coming from other edges, if there are other edges. Along several instances of the loop, the algorithm will simply decide what's the best one.
But it won't do it immediately, because it doesn't consider v alone but the previous step to reach it. So d[v] can be updated several times during the algorithm, following the best paths that it has been creating.

In the code, I use a free Java library called jgrapht. Without the library, which can be downloaded from the official site of the project, and some adjustments to the $CLASSPATH, you won't be able to compile the code.
First, a random graph is created, composed of 5 integer vertices numbered from 0 to 4, and at most 10 random edges. If a pair (source, target) is generated twice, the method addEdge returns null but the result is simply discarded, so the total number of edges can be less than 10. The weights and the starting vertex are random too.
Then the program calls the algorithm and displays the resulted distances. The utility methods are quite easy to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
import org.jgrapht.*;
import org.jgrapht.graph.*;

import java.util.*;

/*
 * Class to represent a vertex in my program
 * This library only files vertices by contents, not using any kind of ID
 * thus denying the possibility of changing a vertex after insertion
 * But I need an ID together with the distance
 */
class VertexPair
{
  public Double distance;
  public int vertex;

  public VertexPair(Double distance, int vertex)
  {
    this.distance = distance;
    this.vertex = vertex;
  }
}

public class Dijkstra
{
  public static void main(String[] args)
  {
    DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> dijkstraGraph;
    dijkstraGraph = new DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge>(DefaultWeightedEdge.class);

    int startVertex = FillGraph(dijkstraGraph);
    System.out.println(dijkstraGraph);
    System.out.println();
    System.out.println("Printing weights");
    PrintWeights(dijkstraGraph);
    System.out.println();
    System.out.println("Showing the minimum possible weight starting from vertex " + startVertex);
    
    DijkstraAlgorithm(dijkstraGraph, startVertex);
  }

  public static void DijkstraAlgorithm(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg, int s)
  {
    /*
     * Initialization step
     */
    Vector<VertexPair> PriorityQueue = new Vector<VertexPair>(); /* useful structure for computing */
    double[] FinalDistances = new double[5]; /* holds the final results to be showed */
    
    for (int i = 0; i < 5; i++)
    {
      if (i == s)
      {
        FinalDistances[i] = 0.0; /* distance of starting vertex is of course zero */
        PriorityQueue.add(new VertexPair(0.0, i));
      }
      else
      {
        FinalDistances[i] = Double.POSITIVE_INFINITY;
        PriorityQueue.add(new VertexPair(Double.POSITIVE_INFINITY, i));
      }
    }

    /*
     * Solving step
     */
    while (!PriorityQueue.isEmpty())
    {
      VertexPair vp = getMinElement(PriorityQueue); /* the vertex with minimum distance in the vector */
      Set<DefaultWeightedEdge> outgoing = wg.outgoingEdgesOf(vp.vertex); /* all edges coming from the vertex */

      for (DefaultWeightedEdge edge : outgoing)
      {
        int v = wg.getEdgeTarget(edge);
        
        if (getDistanceOf(PriorityQueue, v) > vp.distance + wg.getEdgeWeight(edge))
        {
          setDistanceOf(PriorityQueue, v, vp.distance + wg.getEdgeWeight(edge)); /* changes the entry in the vector */
          FinalDistances[v] = vp.distance + wg.getEdgeWeight(edge); /* mirrors the changes here for later */
        }
      }
    }

    System.out.println(Arrays.toString(FinalDistances));
  }

  public static int FillGraph(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg)
  {
    DefaultWeightedEdge[] edges = new DefaultWeightedEdge[10];
    Random generator = new Random();

    for (int i = 0; i < 5; i++)
    {
      wg.addVertex(i);
    }

    for (int i = 0; i < 10; i++)
    {
      int source, target;
      double weight;
      do
      {
        source = generator.nextInt(5);
        target = generator.nextInt(5);
        weight = (double)generator.nextInt(20);
      } while (source == target);
      
      edges[i] = wg.addEdge(source, target);
      if (edges[i] != null)
      {
        wg.setEdgeWeight(edges[i], weight);
      }
    }

    return generator.nextInt(5);
  }

  public static void PrintWeights(DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> wg)
  {
    Set<DefaultWeightedEdge> allEdges = wg.edgeSet();

    for (DefaultWeightedEdge edge : allEdges)
    {
      System.out.println("w(" + wg.getEdgeSource(edge) + "," + wg.getEdgeTarget(edge) + ") = " + wg.getEdgeWeight(edge));
    }
  }

  /*
   * Returns distance of given vertex
   */
  public static double getDistanceOf(Vector<VertexPair> Q, int vertex)
  {
    for (VertexPair vp : Q)
    {
      if (vp.vertex == vertex)
      {
        return vp.distance;
      }
    }

    return Double.NEGATIVE_INFINITY; /* only here for completeness reason, not really useful */
  }

  /*
   * Sets a new distance for the given vertex
   */
  public static void setDistanceOf(Vector<VertexPair> Q, int vertex, double newDis)
  {
    VertexPair toSet = null;

    /*
     * Looks for the right entry in the vector
     */
    for (VertexPair vp : Q)
    {
      if (vp.vertex == vertex)
      {
        toSet = vp;
        break;
      }
    }
    
    /*
     * Changes the distance with newDis
     */
    Q.remove(toSet);
    toSet.distance = newDis;
    Q.add(toSet);
  }

  /*
   * Returns minimum distance element in the vector
   * removing it at the same time
   */
  public static VertexPair getMinElement(Vector<VertexPair> Q)
  {
    Double minDis = Double.POSITIVE_INFINITY;
    VertexPair min = Q.get(0);

    for (VertexPair element : Q)
    {
      if (element.distance < minDis)
      {
        minDis = element.distance;
        min = element;
      }
    }

    Q.remove(min);
    return min;
  }
  
}