【算法】Dijstra

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法】Dijstra，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3188字，纯文字阅读大概需要5分钟。

内容图文

选择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<mark.length;i++)
22             if(!mark[i])
23                 return false;
24         return true;
25     }
26     void dijkstra(final int s){
27         for(int i=0;i<5;i++) {
28             D[i]=new Dist();
29             D[i].pre = s;
30             D[i].length = v[s][i];
31             mark[i]=false;
32         }
33         int u=s;
34         mark[s]=true;
35         while (!AllMarked()){
36             int min=maxInt;
37             for(int i=0;i<5;i++)
38                 if(!mark[i]&&D[i].length>0&&D[i].length<min){
39                 min=D[i].length;
40                 u=i;
41                 }
42             System.out.print("{+"+u+"} ");
43             printD();
44             if(min==maxInt)break;
45             mark[u]=true;
46             for(int i=0;i<5;i++)
47                 if(v[u][i]>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<min){
                min=D[i].length;
                u=i;
                }
            System.out.print("{+"+u+"} ");
            printD();
            if(min==maxInt)break;
            mark[u]=true;
            for(int i=0;i<5;i++)
                if(v[u][i]>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

内容总结

以上是互联网集市为您收集整理的【算法】Dijstra全部内容，希望文章能够帮你解决【算法】Dijstra所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端