1 /**

 2      * 1.对于T中的每个顶点u，找到u的具有最小权重的连接边。所有到u的连接边都存储在queues.get(u)中。queues.get(u).peek()返回拥有最小权值

 3      * 的连接边。如果e.v已经在T中，将e从queues.get(u)中删除。

 4      * 2.比较所有这些边，并且找到那个具有cost[u]+e.getWeight()最小值的边。

 5      */

 6     public ShortestPathTree getShortestPath(int sourceIndex){

 7         List<Integer> T = new ArrayList<Integer>();

 8         T.add(sourceIndex);

 9

10         int numberOfVertices = vertices.size();

11

12         int[] parent = new int[numberOfVertices];

13         parent[sourceIndex] = -1;

14

15         int[] costs = new int[numberOfVertices];

16         for (int i = 0; i < costs.length; i++) {

17             costs[i] = Integer.MAX_VALUE;

18         }

19         costs[sourceIndex] = 0;

20

21         List<PriorityQueue<WeightedEdge>> queues = deepClone(this.queues);

22

23         while (T.size() < numberOfVertices) {

24             int v = -1;

25             int smallestCost = Integer.MAX_VALUE;

26             for (int u:T) {

27                 while(!queues.get(u).isEmpty() &&

28                         T.contains(queues.get(u).peek().v))

29                 {

30                     queues.get(u).remove();

31                 }

32                 if(queues.get(u).isEmpty()){

33                     continue;

34                 }

35                 WeightedEdge e = queues.get(u).peek();

36                 if(costs[u] + e.weight < smallestCost){

37                     v = e.v;

38                     smallestCost = costs[u] + e.weight;

39                     parent[v] = u;

40                 }

41             }

42             T.add(v);

43             costs[v] = smallestCost;

44         }

45         return new ShortestPathTree(sourceIndex, parent, T, costs);

46     }