一张图看懂开发和运营的思维差别
一张图看懂开发和运营的思维差别
有天看到一张小学题目，求最短路径。于是把它发给了女神。
万万没想到女神说，
话说回来那么这道题要怎么解呢，如果你算出来的结果是15，那么就错了。
正确答案是14。
今天介绍一下这道题的解法，Dijkstra最短路。
最短路径算法
假设有这么个图，
要计算从1到6的最短路径。
用Dijkstra算法很简单，我们需要 · 用 6*6矩阵 source[6][6]表示点之间的距离，也就是图中的权值 · 自己与自己的距离为0，无直接连接的距离为∞ · 用 dist[6]表示点1到各个点的最短路径 · 用 flag[6]来记录是否已经求得到其中一个点的最短距离，若已经求得，则为1，否则为0
Dijkstra的思路是， 1 首先将 dist[]初始化，得到点1到它有直接连接的点的距离，没有直接连接的距离为∞ 2 遍历 dist[]，取路径最短且book[index]不为1的点，形成路径 1->index，将 flag[index]变为1 3 取index能直接到达的点，假设点的坐标是 n，如果 dist[0] + dist[index] + source[index][n] > dist[n],则替换掉 dist[n]的值。意思是说有另外一条路径比现有的更短。 4 重复2->3直到 flag[]都变成1.
这里面步骤2->3，称为"松弛"
每次松弛后的结果如下，
dist: [0][1][10][4][2147483647][2147483647] dist: [0][1][8][4][17][19] dist: [0][1][8][4][13][19] dist: [0][1][8][4][13][17] dist: [0][1][8][4][13][17] dist: [0][1][8][4][13][17]
最终得到点1到各个点的距离。 上面的数据是从 sample.txt中读取的，不是一开始那个图的数据哦。有兴趣的朋友可以自己造上面图的数据来测试一下结果是不是14.
贴一下sample数据，把它保存为sample.txt就可以用下面的代码读取了。
6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4
完整的 Dijkstra算法代码如下
import java.util.Scanner;
import java.io.*;
public class Dijkstra {
public static void main(String[] args) {
int source[][] = new int[10][10];
int dist[] = new int[10];
int flag[] = new int[10];
int i,j,n,m,u,v,min;
final int MAX = Integer.MAX_VALUE;
n = m = 0;
try {
Scanner scanner = new Scanner(new FileReader(new File("sample.txt")));
if(scanner.hasNext()) {
n = scanner.nextInt();
m = scanner.nextInt();
}
for(i = 1;i <= n;i++) {
for(j = 1;j <= n;j++){
if(i == j){
source[i][j] = 0;
} else {
source[i][j] = MAX;
}
}
}
while(scanner.hasNext()){
int row = scanner.nextInt();
int column = scanner.nextInt();
source[row][column] = scanner.nextInt();
}
} catch (Exception e) {
System.out.println("error reading file");
return;
}
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i = 1;i <= n;i++) {
dist[i] = source[1][i];
}
//book数组初始化
for(i = 1;i <= n;i++)
flag[i] = 0;
flag[1] = 1;
//Dijkstra算法核心语句
u = 0;
for(i = 1;i <= n-1;i++) {
//找到离1号顶点最近的顶点
min = MAX;
for(j = 1;j <= n;j++) {
if(flag[j] == 0 && dist[j]<min) {
min = dist[j];
u = j;
}
}
flag[u] = 1;
for(v = 1;v <= n;v++) {
if(source[u][v]<MAX) {
if(dist[v]>dist[u]+source[u][v])
dist[v] = dist[u]+source[u][v];
}
}
System.out.print("dist: ");
for(int index = 1;index <= n;index++) {
System.out.print("[" + dist[index] + "]");
}
System.out.println("");
}
//输出最终的结果
System.out.print("final dist: ");
for(int index = 1;index <= n;index++) {
System.out.print("[" + dist[index] + "]");
}
System.out.println("");
}
}