# 漫画：Dijkstra 算法的优化

```/** * Dijkstra最短路径算法 */public static int[] dijkstra(Graph graph, int startIndex) {
//图的顶点数量    int size = graph.vertexes.length;    //创建距离表，存储从起点到每一个顶点的临时距离    int[] distances = new int[size];    //创建前置定点表，存储从起点到每一个顶点的已知最短路径的前置节点    int[] prevs = new int[size];    //记录顶点遍历状态    boolean[] access = new boolean[size];
//初始化最短路径表，到达每个顶点的路径代价默认为无穷大    for(int i=0; i<size; i++){        distances[i] = Integer.MAX_VALUE;    }    //遍历起点，刷新距离表    access[0] = true;    List<Edge> edgesFromStart = graph.adj[startIndex];    for(Edge edge : edgesFromStart)    {        distances[edge.index] = edge.weight;        prevs[edge.index] = 0;    }    //主循环，重复 遍历最短距离顶点和刷新距离表 的操作    for(int i=1; i<size; i++)    {        //寻找最短距离顶点        int minDistanceFromStart = Integer.MAX_VALUE;        int minDistanceIndex = -1;        for(int j=1; j<size; j++)        {            if(!access[j] && distances[j] < minDistanceFromStart)            {                minDistanceFromStart = distances[j];                minDistanceIndex = j;            }        }        if(minDistanceIndex == -1){            break;        }        //遍历顶点，刷新距离表        access[minDistanceIndex] = true;        for(Edge edge : graph.adj[minDistanceIndex])        {            if(access[edge.index]){                continue;            }            int weight = edge.weight;            int preDistance = distances[edge.index];            if(weight != Integer.MAX_VALUE  && (minDistanceFromStart+ weight < preDistance))            {                distances[edge.index] = minDistanceFromStart + weight;                prevs[edge.index] = minDistanceIndex;            }        }    }
return prevs;}
public static void main(String[] args) {    Graph graph = new Graph(7);    initGraph(graph);    int[] prevs = dijkstra(graph, 0);    printPrevs(graph.vertexes, prevs, graph.vertexes.length-1);}
private static void printPrevs(Vertex[] vertexes, int[] prev, int i){    if(i>0){        printPrevs(vertexes, prev, prev[i]);    }    System.out.println(vertexes[i].data);}
/** * 图的顶点 */private static class Vertex {    String data;    Vertex(String data) {        this.data = data;    }}
/** * 图的边 */private static class Edge {    int index;    int weight;    Edge(int index, int weight) {        this.index = index;        this.weight = weight;    }}
/** * 图 */private static class Graph {    private Vertex[] vertexes;    private LinkedList<Edge> adj[];
private static void initGraph(Graph graph){    graph.vertexes[0] = new Vertex("A");    graph.vertexes[1] = new Vertex("B");    graph.vertexes[2] = new Vertex("C");    graph.vertexes[3] = new Vertex("D");    graph.vertexes[4] = new Vertex("E");    graph.vertexes[5] = new Vertex("F");    graph.vertexes[6] = new Vertex("G");

—————END—————

0 条评论

• ### 漫画：图的 “最短路径” 问题

第1步，创建距离表。表中的Key是顶点名称，Value是从起点A到对应顶点的已知最短距离。但是，一开始我们并不知道A到其他顶点的最短距离是多少，Value默认是...

• ### 漫画：什么是 “图”？

举个栗子，大家一定都用过微信，假设你的微信朋友圈中有若干好友：张三、李四、王五、赵六、七大姑、八大姨。

• ### 漫画：图的 “最短路径” 问题

第1步，创建距离表。表中的Key是顶点名称，Value是从起点A到对应顶点的已知最短距离。但是，一开始我们并不知道A到其他顶点的最短距离是多少，Value默认是...

• ### 数据结构——图相关概念

可是现实生活中，好多关系不再是一对一或一对多，比如人和人之间的关系，会互相认识，就要考虑多对多的情况。这就是今天要介绍的——图。

• ### 各数据结构的基本概念和术语汇总

线性表中任一数据元素都可以 随机存取 ，所以 线性表的顺序存储结构是一种随机存取的存储结构。

• ### 贺建奎给自己做了三次“基因编辑”：想当中国爱因斯坦，却变成生物狂人

贺建奎，来自湖南娄底，家境贫寒，爸妈务农。根据媒体报道，他从小迷恋物理学，立志要成为中国的爱因斯坦。

• ### 一文简述ResNet及其多种变体

在 AlexNet [1] 取得 LSVRC 2012 分类竞赛冠军之后，深度残差网络（Residual Network, 下文简写为 ResNet）[2] 可...