Dijkstra

/**
* Kürzeste Wege in einem Graphen ermitteln
*
* @author neubauer 03.12.2022 create
*/
public class Dijkstra
{
//    grün = leere Menge
//    gelb = ausgangselement
//    distanz von v = 0
//    so lange menge der gelben elemente nicht leer ist
//        wähle das element aus den gelben elementen mit der geringsten Entfernung als w
//        färbe w grün
//        für alle nachfolger von w als wI
//            wenn wI nicht gelb oder grün
//                färbe die kante rot,
//                färbe wI gelb; Distanz  von wI ist distanz von w + kosten des übergangs von w zu wI
//            sonst wenn wI gelb
//                wenn distanz von wI kleiner als distanz von w + kosten des übergangs von w zu wI
//                    färbe die kante rot,
//                    färbe die bisher rote kante zu wI gelb
//                    dist(wI) = dist(w)+cost(w,wI)
//                sonst
//                    färbe w, wI gelb
//            sonst 
//                färbe w, wI gelb

   private static final int N = 6;

   enum Status
   {
       GRAY,
       RED,
       YELLOW,
       GREEN;
   }

   static Node[] graph = new Node[N];

   static double[] dist = new double[N];
   static Node[] father = new Node[N];
   static boolean[] green = new boolean[N];

   static class Node
   {
       private char name;
       private NodeLink successorLeft;
       private NodeLink successorRight;
       private Status status = Status.GRAY;
       private int distance;

       Node(final char c)
       {
           this.name = c;
       }

       public char getName()
       {
           return name;
       }

       public void setName(final char name)
       {
           this.name = name;
       }

       public NodeLink getSuccessorLeft()
       {
           return successorLeft;
       }

       public void setSuccessorLeft(final NodeLink successorLeft)
       {
           this.successorLeft = successorLeft;
       }

       public NodeLink getSuccessorRight()
       {
           return successorRight;
       }

       public void setSuccessorRight(final NodeLink successorRight)
       {
           this.successorRight = successorRight;
       }

       public Status getStatus()
       {
           return status;
       }

       public void setStatus(final Status status)
       {
           this.status = status;
       }

       public int getDistance()
       {
           return distance;
       }

       public void setDistance(final int distance)
       {
           this.distance = distance;
       }
   }

   static class NodeLink
   {
       private int targetNodeIndex;
       private int cost;
       private Status status = Status.GRAY;

       NodeLink(final int target, final int cost)
       {
           this.targetNodeIndex = target;
           this.cost = cost;
       }

       public int getTargetNodeIndex()
       {
           return targetNodeIndex;
       }

       public void setTargetNodeIndex(final int targetNodeIndex)
       {
           this.targetNodeIndex = targetNodeIndex;
       }

       public int getCost()
       {
           return cost;
       }

       public void setCost(final int cost)
       {
           this.cost = cost;
       }

       public Status getStatus()
       {
           return status;
       }

       public void setStatus(final Status status)
       {
           this.status = status;
       }

   }

   static class LinkIterator
   {
       private boolean leftVisited = false;
       private boolean rightVisited = false;
       private Node node;

       LinkIterator(final Node node)
       {
           this.node = node;
       }

       public boolean hasNext()
       {
           return !leftVisited || !rightVisited;
       }

       public NodeLink getNext()
       {
           if (!leftVisited)
           {
               leftVisited = true;
               return node.getSuccessorLeft();
           }
           if (!rightVisited)
           {
               rightVisited = true;
               return node.getSuccessorRight();
           }
           return null;
       }
   }

   public static void main(final String[] args)
   {
       initNodes();

       dijkstra();

       output();
   }

   private static void output()
   {
       for (int i = 0; i < graph.length; i++)
       {
           System.out.println(graph[i].getName() + ": " + graph[i].getDistance());
           LinkIterator lit = new LinkIterator(graph[i]);
           while (lit.hasNext())
           {
               NodeLink next = lit.getNext();
               if (next != null && next.getStatus() == Status.RED)
               {
                   System.out.println("Link to " + next.getTargetNodeIndex() + " Status " + next.getStatus() + " cost " + next.getCost());
               }
           }
       }
   }

   private static void dijkstra()
   {
       Node v = graph[0];
       v.setStatus(Status.YELLOW);
       v.setDistance(0);

       while (hasYellowNodes(graph))
       {
           Node w = getNearestYellow(graph);
           w.setStatus(Status.GREEN);
           LinkIterator lit = new LinkIterator(w);
           while (lit.hasNext())
           {
               NodeLink next = lit.getNext();
               if (next != null)
               {
                   Node wI = graph[next.getTargetNodeIndex()];
                   if (wI.getStatus() != Status.YELLOW && wI.getStatus() != Status.GREEN)
                   {
                       next.setStatus(Status.RED);
                       wI.setStatus(Status.YELLOW);
                       wI.setDistance(w.getDistance() + next.getCost());
                   }
                   else if (wI.getStatus() == Status.YELLOW)
                   {
                       if ((w.getDistance() + next.getCost()) < wI.getDistance())
                       {
                           next.setStatus(Status.RED);
                           removeRedLink(graph, wI);
                           wI.setDistance(w.getDistance() + next.getCost());
                       }
                       else
                       {
                           next.setStatus(Status.YELLOW);
                       }
                   }
                   else
                   {
                       next.setStatus(Status.YELLOW);
                   }
               }
           }
       }
   }

   private static void removeRedLink(final Node[] graph, final Node wI)
   {
       boolean removed = false;
       for (int i = 0; i < graph.length; i++)
       {
           LinkIterator lit = new LinkIterator(graph[i]);
           while (lit.hasNext())
           {
               NodeLink candidate = lit.getNext();
               if (candidate.getStatus() == Status.RED && graph[candidate.getTargetNodeIndex()].getName() == wI.getName())
               {
                   candidate.setStatus(Status.YELLOW);
                   removed = true;
                   break;
               }
           }
           if (removed)
           {
               break;
           }
       }
   }

   private static Node getNearestYellow(final Node[] nodes)
   {
       Node result = null;
       if (hasYellowNodes(nodes))
       {
           result = nodes[firstYellowNode(nodes)];
           for (int i = firstYellowNode(nodes); i < nodes.length; i++)
           {
               if (nodes[i].getStatus() == Status.YELLOW && nodes[i].getDistance() < result.getDistance())
               {
                   result = nodes[i];
               }
           }
       }
       return result;
   }

   private static boolean hasYellowNodes(final Node[] nodes)
   {
       boolean result = false;
       if (nodes != null && nodes.length > 0)
       {
           for (int i = 0; i < nodes.length; i++)
           {
               if (nodes[i].getStatus() == Status.YELLOW)
               {
                   result = true;
                   break;
               }
           }
       }
       return result;
   }

   private static int firstYellowNode(final Node[] nodes)
   {
       int result = -1;
       if (nodes != null && nodes.length > 0)
       {
           for (int i = 0; i < nodes.length; i++)
           {
               if (nodes[i].getStatus() == Status.YELLOW)
               {
                   result = i;
                   break;
               }
           }
       }
       return result;
   }

   private static void initNodes()
   {
       char c = 'A';
       for (int i = 0; i < N; i++)
       {
           graph[i] = new Node(c++);
       }
       // 0 1 2 3 4 5
       // A B C D E F
       graph[0].setSuccessorLeft(new NodeLink(1, 30));
       graph[0].setSuccessorRight(new NodeLink(5, 90));

       graph[1].setSuccessorLeft(new NodeLink(2, 10));
       graph[1].setSuccessorRight(new NodeLink(3, 40));

       graph[2].setSuccessorLeft(new NodeLink(0, 40));
       graph[2].setSuccessorRight(new NodeLink(5, 10));

       graph[3].setSuccessorLeft(new NodeLink(4, 30));

       graph[5].setSuccessorLeft(new NodeLink(4, 20));
   }

}