今天经过了将近两个小时的的努力，将昨天的迪杰斯特拉算法改到了Servlst上面，并进行了实现，努力没有白费，可以查询出来，后期优化一下界面我觉得就可以了
以下为界面展示：选取的嘉华路到柳辛庄
具体实现方法为：在网上找到的具体代码，进行展示，进行修改，建立与之匹配的数据库，建立连接，然后实现。
网上的具体代码：(48条消息) 迪杰斯特拉（Dijkstra）算法 Java实现（最短路径）_初始时,s只包括起点s_CmdSmith的博客-CSDN博客
数据库建立：适应上述代码而特地建立的数据库
1：站点id唯一且存在
2：建立网状图
代码实现：具体的servlet
package com.itheima.web;
import com.itheima.pojo.Line;
import com.itheima.pojo.ShortLine;
import com.itheima.service.Service;
import javax.servlet.*;
import javax.servlet.http.*;
import javax.servlet.annotation.*;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
@WebServlet("/ShortistLine1Servlet")
public class ShortistLine1Servlet extends HttpServlet
{
private Service service = new Service();
private int[][] matrix ;
/**
* 表示正无穷
*/
private int MAX_WEIGHT = Integer.MAX_VALUE;
/**
* 顶点集合
*/
private String[] vertexes;
/**
* 创建图2
*/
private static String Line = "最短路径: ";
private static String Endstop = "";
private void createGraph2(int index)
{
matrix = new int[index][index];
for (int i = 0; i < index; i++) {
for (int j = 0; j < index; j++) {
matrix[i][j] = Integer.MAX_VALUE;
}
}
vertexes = new String[index];
List<com.itheima.pojo.Line> lines = new ArrayList<Line>();
lines = service.find();
System.out.println("lines = " + lines);
for (Line line : lines) {
System.out.println("line.getLine1() = " + ((line.getLine1() - 1)));
System.out.println("line.getLine2() = " + ((line.getLine2() - 1)));
matrix[line.getLine1() - 1][line.getLine2() - 1] = 1;
matrix[line.getLine2() - 1][line.getLine1() - 1] = 1;
}
// for (int i = 0; i < index; i++) {
// for (int j = 0; j < index; j++) {
// if (matrix[i][j] == Integer.MAX_VALUE) {
// System.out.print("0 ");
// } else {
// System.out.print(matrix[i][j] + " ");
// }
// }
// System.out.println();
// }
//
List<ShortLine> shortLines = new ArrayList<ShortLine>();
shortLines = service.getAll();
System.out.println("shortLines = " + shortLines);
int count = 0;
for (ShortLine shortLine : shortLines) {
vertexes[count++] = shortLine.getName();
System.out.println(shortLine.getName());
}
}
public void dijkstra(int vs)
{
vs = vs - 1;
// flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取
boolean[] flag = new boolean[vertexes.length];
// U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)，与 flag配合使用,flag[i] == true 表示U中i顶点已被移除
int[] U = new int[vertexes.length];
// 前驱顶点数组,即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
int[] prev = new int[vertexes.length];
// S的作用是记录已求出最短路径的顶点
String[] S = new String[vertexes.length];
// 步骤一：初始时，S中只有起点vs；U中是除vs之外的顶点，并且U中顶点的路径是"起点vs到该顶点的路径"。
for (int i = 0; i < vertexes.length; i++) {
flag[i] = false; // 顶点i的最短路径还没获取到。
U[i] = matrix[vs][i]; // 顶点i与顶点vs的初始距离为"顶点vs"到"顶点i"的权。也就是邻接矩阵vs行的数据。
prev[i] = 0; //顶点i的前驱顶点为0
}
// 将vs从U中“移除”（U与flag配合使用）
flag[vs] = true;
U[vs] = 0;
// 将vs顶点加入S
S[0] = vertexes[vs];
// 步骤一结束
//步骤四：重复步骤二三，直到遍历完所有顶点。
// 遍历vertexes.length-1次；每次找出一个顶点的最短路径。
int k = 0;
for (int i = 1; i < vertexes.length; i++)
{
// 步骤二：从U中找出路径最短的顶点，并将其加入到S中（如果vs顶点到x顶点还有更短的路径的话，那么
// 必然会有一个y顶点到vs顶点的路径比前者更短且没有加入S中
// 所以，U中路径最短顶点的路径就是该顶点的最短路径）
// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
int min = MAX_WEIGHT;
for (int j = 0; j < vertexes.length; j++)
{
if (flag[j] == false && U[j] < min)
{
min = U[j];
k = j;
}
}
//将k放入S中
S[i] = vertexes[k];
//步骤二结束
//步骤三：更新U中的顶点和顶点对应的路径
//标记"顶点k"为已经获取到最短路径（更新U中的顶点，即将k顶点对应的flag标记为true）
flag[k] = true;
//修正当前最短路径和前驱顶点（更新U中剩余顶点对应的路径）
//即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (int j = 0; j < vertexes.length; j++)
{
//以k顶点所在位置连线其他顶点，判断其他顶点经过最短路径顶点k到达vs顶点是否小于目前的最短路径，是，更新入U，不是，不做处理
int tmp = (matrix[k][j] == MAX_WEIGHT ? MAX_WEIGHT : (min + matrix[k][j]));
if (flag[j] == false && (tmp < U[j]))
{
U[j] = tmp;
//更新 j顶点的最短路径前驱顶点为k
prev[j] = k;
}
}
//步骤三结束
}
//步骤四结束
// 打印dijkstra最短路径的结果
System.out.println("起始顶点：" + vertexes[vs]);
for (int i = 0; i < vertexes.length; i++)
{
//System.out.println(Endstop);
if (vertexes[i].equals(Endstop)) {
Line += vertexes[vs] + "->";
//System.out.print("最短路径（" + vertexes[vs] + "," + vertexes[i] + "):" + U[i] + " ");
List<String> path = new ArrayList<>();
int j = i;
while (true) {
path.add(vertexes[j]);
if (j == 0)
break;
j = prev[j];
}
for (int x = path.size() - 2; x >= 0; x--) {
if (x == 0) {
Line += path.get(x);
//System.out.println(path.get(x));
} else {
Line += path.get(x);
Line += "->";
// System.out.print(path.get(x) + "->");
}
}
}
}
}
@Override
protected void doGet(HttpServletRequest request, HttpServletResponse response)throws ServletException, IOException
{
request.setCharacterEncoding("UTF-8");
String begin=request.getParameter("begin");
String end=request.getParameter("end");
System.out.println("begin = " + begin );
System.out.println("end = " + end);
ShortistLine1Servlet dij = new ShortistLine1Servlet();
// dij.createGraph1(6);
Endstop = end;
dij.createGraph2(60);
int id = service.Stationquery(begin);
System.out.println("id = " + id );
dij.dijkstra(id);
System.out.println(Line);
request.setAttribute("Line",Line);
Line = "最短路径: ";
request.getRequestDispatcher("result.jsp").forward(request,response);
}
@Override
protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
this.doGet(request, response);
}
}