数据结构（12）Dijkstra算法JAVA版：图的最短路径问题

小咪咪 2023-09-23 17:39 27阅读 0赞

**目录**

12.1.概述

12.1.1.无权图的最短路径

12.1.2.带权图的最短路径

1.单源最短路径

2.多源最短路径

12.2.代码实现

--------------------

## 12.1.概述 ##

### 12.1.1.无权图的最短路径 ###

无权图的最短路径，即最少步数，使用BFS+贪心算法来求解最短路径，比较好实现，此处不做展开讨论。

![cb5502e3ea764783ad658c7759691e4f.png][]

### 12.1.2.带权图的最短路径 ###

有权图的最短路径，不考虑权重为负数的情况，因为权重为负数的情况极有可能出现负值圈，在这个圈子上形成环路，最短路径是无限兜圈，趋于负无穷。

所以此处我们只考虑权重不为负数的带权图的最短路径求解问题。带权图的最短路径求解问题主要求两种最短路径：

*  单源最短路径，某个点到全图各点之间的最短路径。
 *  多源最短路径，遍历全图的最短路径。

单源最短路径用Dijkstra算法求解，多源最短路径用Floyd算法求解。

#### 1.单源最短路径 ####

单源最短路径用Dijkstra算法求解，Dijkstra算法其本质是个贪心算法。整个过程就是选择局部最优解，组成最后的解。

以下展示一个Dijkstra求解v1的单源最短路径的过程：

![d3c666b361f74b538f71cafe30e5f7b4.png][]

记录两个值：

distance，到某个结点的最短距离，初始化值为无穷大，表示暂时未记录。

route，全局最短路径，初始化值为-1，表示暂时未记录。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>下标</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>distance</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
  </tr> 
  <tr> 
   <td>route</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
  </tr> 
 </tbody> 
</table>

v1开始，刷新distance和route的值：

v1—>v1，distance为0

v1—>v2，distance为2<∞，将2刷新为v1—>v2的最短距离，将1（指代v1）刷新为最短路径。

v4同理……

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>下标</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>distance</td> 
   <td>0</td> 
   <td>2</td> 
   <td>无穷大</td> 
   <td>1</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
   <td>无穷大</td> 
  </tr> 
  <tr> 
   <td>route</td> 
   <td>-1</td> 
   <td>1</td> 
   <td>-1</td> 
   <td>1</td> 
   <td>-1</td> 
   <td>-1</td> 
   <td>-1</td> 
  </tr> 
 </tbody> 
</table>

扫描distance表发现distance最小的v4，于是将v4上得到的数据刷新进distance和route：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>下标</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>distance</td> 
   <td>0</td> 
   <td>2</td> 
   <td>3</td> 
   <td>1</td> 
   <td>3</td> 
   <td>9</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>route</td> 
   <td>-1</td> 
   <td>1</td> 
   <td>4</td> 
   <td>1</td> 
   <td>4</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
 </tbody> 
</table>

一直重复上面步骤，直到图里所有结点都被遍历一次，会得到如下结果：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>下标</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>distance</td> 
   <td>0</td> 
   <td>2</td> 
   <td>3</td> 
   <td>1</td> 
   <td>3</td> 
   <td>6</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>route</td> 
   <td>-1</td> 
   <td>1</td> 
   <td>4</td> 
   <td>1</td> 
   <td>4</td> 
   <td><span style="color:#fe2c24;">7</span></td> 
   <td>4</td> 
  </tr> 
 </tbody> 
</table>

distance记录的是v1到每个结点的最短路径，route里面记录的最大值是全局遍历一遍的最短路径。

#### 2.多源最短路径 ####

多源最短路径用floyd算法求解，多源最短路径不能只关注于当前最优解，还要关注全局最优解，求解此类问题一般使用动态规划，floyd算法就是个求解多源最短路径的经典动态规划算法。本文主要论述Dijkstra算法，floyd算法暂时不展开。

## 12.2.代码实现 ##

以遍历如下无向图为例（为什么不遍历上面的例子喃？因为代码是很久前写的了。上面的例子是写文的时候新写的，偷个懒不想改代码了~嘿嘿）：

![b978f463464f43d9ad937d6112a796f2.png][]

public class Dijkstra {
        static int[][] graph;
        static int[] dist;
        static int[] path=new int[7];
        static boolean[] isUsed=new boolean[7];
        static {
            graph=new int[][]{
                    {0,1,4,3,0,0,0},
                    {1,0,3,0,0,0,0},
                    {4,3,0,2,1,5,0},
                    {3,0,2,0,2,0,0},
                    {0,0,1,2,0,0,0},
                    {0,0,5,0,0,0,2},
                    {0,0,0,0,0,2,0}
            };
            dist=new int[]{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE};
        }
        public static void dijkstra(){
            while(true){
                //判断节点是否已经全部纳入
                if(isOver()){
                    break;
                }
                //寻找未纳入的dist最小节点
                int i=findMin();
                //设置为已遍历状态
                isUsed[i]=true;
                //遍历该节点邻接节点
                for (int j=0;j<graph[i].length;j++) {
                    if(graph[i][j]!=0&&isUsed[j]==false){
                        //更新dist、path
                        flashDistAndPath(i,j);
                    }
                }
            }
        }
    
        public static int findMin(){
            int min=Integer.MAX_VALUE;
            int index=-1;
            for(int i=0;i<dist.length;i++){
                if(min>dist[i]&&isUsed[i]==false){
                    min=dist[i];
                    index=i;
                }
            }
            return index;
        }
    
        //之前的dist值一定是之前该节点到根节点的最短路径开销
        public static void flashDistAndPath(int i,int j){
                if(isUsed[j]==false) {
                    if (graph[i][j] + dist[i] < dist[j]) {
                        dist[j] = graph[i][j] + dist[i];
                        path[j] = j;
                    }
                }
        }
    
        public static boolean isOver(){
            int trues=0;
            for (boolean isused:isUsed) {
                if(isused==true){
                    trues++;
                }
            }
            if(trues==dist.length){
                return true;
            }
            return false;
        }
    
        public static void main(String[] args) {
            isUsed[0]=true;
            dist[1]=1;
            dist[2]=4;
            dist[3]=3;
    
            path[1]=0;
            path[2]=0;
            path[3]=0;
            dijkstra();
            for (int i=0;i<dist.length;i++){
                System.out.println(dist[i]);
            }
        }
    }

[cb5502e3ea764783ad658c7759691e4f.png]: https://img-blog.csdnimg.cn/cb5502e3ea764783ad658c7759691e4f.png
[d3c666b361f74b538f71cafe30e5f7b4.png]: https://img-blog.csdnimg.cn/d3c666b361f74b538f71cafe30e5f7b4.png
[b978f463464f43d9ad937d6112a796f2.png]: https://img-blog.csdnimg.cn/b978f463464f43d9ad937d6112a796f2.png