Dijkstra算法求带权图的单源最短路径

悠悠 2022-08-08 11:46 192阅读 0赞

### Dijkstra算法: ###

### 给出一个带权无向图，要求指定顶点到图中每一个点的最短路径。 ###

首先我们定义一个邻接矩阵c，c\[i\]\[j\]用来表示从顶点i到顶点j的权重，用一个一维数组prev\[\]来记录指定节点的父节点，如果不需要输出路径的轨迹，那么就不需要用到这个数组。用一个vis的boolean数组存储每一个节点是否被访问过。用一个dist\[\]数组来存储指定顶点到每一个顶点的最短路径。

1、搜索判断指定顶点v到每一个顶点是否有边连接，并在搜索的过程中吧vis数组初始化为false（Java则省略这一步），如果两个顶点之间有边连接，那么就令prev\[i\]=v；令dist\[v\]=0，vis\[v\]=true;

2、用一个循环来寻找剩下的n-1个顶点到指定顶点的最短路。在dist数组中找到一条没被访问过的到指定顶点的最短路径，然后记录该顶点u，把该顶点的vis设置为true；

3、在第二步找到的顶点u中，寻找与顶点u有边相连而且又没有被访问过的顶点，然后计算该顶点从顶点u这条路径到达顶点v的距离：

if(!vis[j]&&c[u][j]>0) {
    
     
    
    int tempDis = dist[u] + c[u][j];
    
    if(tempDis<dist[j]) {
    
    dist[j] = tempDis;
    
    prev[j] = u;
    
    }
    
    }

完整代码如下：

public class Dijkstra {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[][] c = {
    			{0, 10, 0, 30, 100},
    			{10, 0, 50, 0, 0},
    			{0, 50, 0, 20, 10},
    			{30, 0, 20, 0, 60},
    			{100, 0, 10, 60, 0}
    		};
    		dijkstra(0, c);
    	}
    	
    	public static void dijkstra(int v, int[][] c) {
    		int[] dist = new int[c.length];
    		int[] prev = new int[c.length];
    		boolean[] vis = new boolean[c.length];
    		for(int i = 0; i < dist.length; i++) {
    			dist[i] = Integer.MAX_VALUE;
    		}
    		for(int i = 0; i < dist.length; i++) {
    			dist[i] = c[v][i] == 0 ? Integer.MAX_VALUE : c[v][i];
    			if(dist[i] > 0) {
    				prev[i] = v;
    			}
    		}
    		dist[v] = 0;
    		vis[v] = true;
    		prev[v] = -1;
    		
    		for(int i = 1; i < dist.length; i++) {
    			int curMin = Integer.MAX_VALUE;
    			int u = 0;
    			//贪心算法找一个到指定顶点距离最短的点
    			for(int j = 0; j < dist.length; j++) {
    				if(!vis[j] && dist[j] < curMin) {
    					curMin = dist[j];
    					u = j;
    				}
    			}
    			//令vis[u] = true，因为已经访问过顶点u了
    			vis[u] = true;
    			//在找到该顶点u后，更新与u相邻的点到顶点v的距离
    			for(int j = 0; j < dist.length; j++) {
    				if(!vis[j] && c[u][j] > 0) {
    					int tempDis = dist[u] + c[u][j];
    					if(tempDis < dist[j]) {
    						dist[j] = tempDis;
    						prev[j] = u;
    					}
    				}
    			}
    		}
    		
    		//打印操作........
    		for(int i = 0; i < dist.length; i++) {
    			System.out.print(dist[i] + " ");
    		}
    		System.out.println();
    		for(int i = 0; i < dist.length; i++) {
    			System.out.print(prev[i] + " ");
    		}
    		System.out.println();
    		
    	}
    
    }