Dijkstra算法

package com.company.algs.graph.dijkstra;


import java.util.*;
/** 
来 自 
N o w  J a v a  .   c o m
**/


public class Dijkstra {

    private static class Edge {

        private Vertex to;

        private int weight;


        Edge(Vertex to, int weight) {

            this.to = to;

            this.weight = weight;

        }

    }


    private static class Vertex {

        static final int INFINITE = Integer.MAX_VALUE;


/* from 
nowjava.com*/



        private List<Edge> outEdges;

        private String name;

        private Vertex bestParent;

        private int mark = INFINITE;

        private boolean visited;


        Vertex(String name) {

            this.name = name;

        }


        @Override

        public String toString() {

            return "Vertex{" + "name='" + name + '\'' + ", visited="

                    + visited + '}';

        }

    }


    private void execute(Set<Vertex> vertices) {

        Comparator<Vertex> comparator = new Comparator<Vertex>() {

            @Override

            public int compare(Vertex o1, Vertex o2) {

                return o1.mark < o2.mark ? -1 : (o1.mark > o2.mark ? 1 : 0);

            }

        };


        while (!vertices.isEmpty()) {

            Vertex vertex = Collections.min(vertices, comparator);

            for (Edge edge : vertex.outEdges) {

                if (!edge.to.visited

                        && vertex.mark + edge.weight < edge.to.mark) {

                    edge.to.mark = vertex.mark + edge.weight;

                    edge.to.bestParent = vertex;

                }

            }

            vertices.remove(vertex);

            vertex.visited = true;

        }

    }


    public static void main(String[] args) {

        Vertex vertexA = new Vertex("A");

        Vertex vertexB = new Vertex("B");

        Vertex vertexC = new Vertex("C");

        Vertex vertexD = new Vertex("D");

        Vertex vertexE = new Vertex("E");


        vertexA.outEdges = Arrays.asList(new Edge(vertexB, 1), new Edge(

                vertexC, 2), new Edge(vertexE, 44));


        vertexB.outEdges = Collections.singletonList(new Edge(vertexD, 4));

        vertexC.outEdges = Collections.singletonList(new Edge(vertexE, 23));

        vertexD.outEdges = Collections.singletonList(new Edge(vertexE, 5));

        vertexE.outEdges = Collections.emptyList();


        vertexC.mark = 0;