最短路径算法
1 public class Dijkstra {
2
3 static final int maxWeight = 9999;
4
5 //distance保存了从起始节点到每一个节点的最短距离
6 //path保存了路径
7 //v0是起始节点
8 public static void dijkstra(MyAdjGraphic g,int v0,int[]
distance,int[] path)
9 throws Exception
10 {
11 int n = g.getNumOfVertice();//结点数量
12 int[] s = new int[n]; //标示结点是否已被访问的数组
13 int minDis; //每次找到的最短路径
14 int u=0; //下一次最短路径对应的结点的下标
15
16 //初始化，把初始节点距离所有节点的信息初始化
17 for(int i=0;i<n;i++)
18 {
19 distance[i] = g.getWeightOfEdges(v0, i);
20 s[i] = 0; //未访问
21 if(i!=v0&&distance[i]<maxWeight)
22 {
23 path[i]= v0;
24 }
25 else
26 {
27 path[i]=-1;
28 }
29 }
30 s[0]=1; //标记为已访问
31
32 //下面是一个大循环，找出每个节点距离初始节点的最短距离
33 for(int i=1;i<n;i++)
34 {
35 minDis = maxWeight;
36 //从还未访问过的节点中，选择一个距起始节点最近的点
37 for(int j=0;j<n;j++)
38 {
39 if(distance[j]!=-1) //说明有边存在
40 {
41 //结点未访问，并且小于当前最小路径
42 if(s[j]==0&&distance[j]<minDis)
43 {
44 u = j;
45 minDis = distance[j];
46 }
47 }
48 }
49 //如果节点都访问到了，退出
50 if(minDis==maxWeight)
51 {
52 return ;
53 }
54
55 //把这个未访问的节点设置为访问过了
56 s[u]=1;//标记为已访问
57
58 //然后以这个节点为主，进一步找最小的路径与前面已有的路径比较，取最小的。
59 for(int j=0;j<n;j++)
60 {
61 if(g.getWeightOfEdges(u, j)!=-1) //有边存在
62 {
63 //说明起始节点还未能到达此节点
64 if(distance[j]==-1) //未访问过
65 {
66
if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight)
67 {
68 distance[j] =
distance[u]+g.getWeightOfEdges(u, j);
69 //记录找到的节点的前一个节点，记录最小路径
70 path[j]=u;
71 }
72 }
73 //若以前访问过，则比较哪一条路径比较短
74 else
75 {
76
//因为以前起始节点也路过这个，因此要把当前的路径长度和以前的路径长度进行比较
77
if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight &&
distance[u]+g.getWeightOfEdges(u, j)<distance[j])
78 {
79 distance[j] =
distance[u]+g.getWeightOfEdges(u, j);
80 //记录找到的节点的前一个节点，记录最小路径
81 path[j]=u;
82 }
83 }
84 }
85 //一个大循环下来，distance里存放的是起始节点到目前能到达且未访问节点的全部距离，
86 然后再用起初的循环找出距离最小的且未访问的点作为主，进而继续寻找
87 }
88
89 }
90
91 }
92 }
投递牛客等公司8个岗位