选择V-S中的点加入S时用了贪心思想，即求d[]中legth最小且未被标记（未加入加入S）的点。

一点都没优化的实现：

1 import java.lang.reflect.Array; 2  3 /** 4  * Created by yueli on 2018/10/14. 5  */ 6 public class Dijkstra { 7     boolean mark[]=new boolean[5]; 8     int v[][]={
    {0,10,-1,30,100}, {-1,0,50,-1,-1},{-1,-1,0,-1,10},{-1,10,20,0,60},{-1,-1,-1,-1,0}}; 9     class Dist{10         public int pre;11         public int length;12         public Dist(){}13         public Dist(int pre,int length){14             this.pre=pre;15             this.length=length;16         }17     }18     int maxInt=0xfffffff;19     public Dist D[]=new Dist[5];20     boolean AllMarked(){21         for(int i=0;i
      
       0&&D[i].length
       
        0&&(D[i].length>D[u].length+v[u][i]||D[i].length<0)){48                     D[i].length=D[u].length+v[u][i];49                     D[i].pre=u;50                 }51         }52     }53     void printD(){54         for(int i=0;i<5;i++){55             System.out.print("pre:"+D[i].pre+" length:"+D[i].length+" ");56         }57         System.out.println();58     }59     void printV(){60         for(int i=0;i<5;i++) {61             for (int j = 0; j < 5; j++)62                 System.out.print(v[i][j]+" ");63             System.out.println();64         }65     }66     public static void main(String[] args) {67         Dijkstra dijkstra=new Dijkstra();68         dijkstra.printV();69         dijkstra.dijkstra(0);70     }71 }
       
      

void dijkstra(final int s){        for(int i=0;i<5;i++) {            D[i]=new Dist();            D[i].pre = s;            D[i].length = v[s][i];            mark[i]=false;        }        int u=s;        mark[s]=true;        while (!AllMarked()){            int min=maxInt;            for(int i=0;i<5;i++)                if(!mark[i]&&D[i].length>0&&D[i].length
     
      0&&(D[i].length>D[u].length+v[u][i]||D[i].length<0)){                    D[i].length=D[u].length+v[u][i];                    D[i].pre=u;                }        }    }
     

0 10 -1 30 100 -1 0 50 -1 -1 -1 -1 0 -1 10 -1 10 20 0 60 -1 -1 -1 -1 0 {+1} pre:0 length:0 pre:0 length:10 pre:0 length:-1 pre:0 length:30 pre:0 length:100 {+3} pre:0 length:0 pre:0 length:10 pre:1 length:60 pre:0 length:30 pre:0 length:100 {+2} pre:0 length:0 pre:0 length:10 pre:3 length:50 pre:0 length:30 pre:3 length:90 {+4} pre:0 length:0 pre:0 length:10 pre:3 length:50 pre:0 length:30 pre:2 length:60 Process finished with exit code 0

#include 
     
      #include
      
       using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */bool allMarked(bool *mark,const int n){    for(int i=0;i
       

q; bool *mark=new bool[n]; q.push(s);mark[s]=1; while(!q.empty()||!allMarked(mark,n)){ while(!q.empty()){ s=q.front(); q.pop(); cout<

<<" "; for(int i=0;i