使用SQL语句解决最短路径问题-SQLite

发布时间 2023-03-23 01:54:45作者: 冰稀饭Aurora

使用SQL语句解决最短路径问题-SQLite上如何实现

今天成功实现了sqlite端的最短路径,同web端大同小异:

使用的SQL语句:

WITH RECURSIVE transfer(start_station, stop_station, stops, paths) AS (
                        SELECT station_name, next_station, 1 stops, 
                               line_name||station_name||'->'||line_name||next_station AS paths
                        FROM bj_subway 
                        WHERE station_name = ? 
                        UNION ALL  
                        SELECT t.start_station, s.next_station, stops+1, paths||'->'||s.line_name||s.next_station
                        FROM transfer t 
                        JOIN bj_subway s  
                        ON (t.stop_station = s.station_name AND instr(paths, s.next_station)=0)
                        )
                        SELECT  
                        FROM transfer 
                        WHERE stop_station = ?;

以下是示例代码:

package com.example.dataapplication.DataBase;

import android.annotation.SuppressLint;
import android.content.Context;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;

import com.example.dataapplication.Infomation.SubwayBean;

import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;

public class CRUD {
    private DBHelper dbHelper;

    public CRUD (Context context){dbHelper = new DBHelper(context);}

    @SuppressLint("Range")
    public SubwayBean BestTransferStation(String station1, String station2){

        SQLiteDatabase db = dbHelper.getReadableDatabase();
        String sql =
                "WITH RECURSIVE transfer(start_station, stop_station, stops, paths) AS (\n" +
                        "SELECT station_name, next_station, 1 stops, \n" +
                        "       line_name||station_name||'->'||line_name||next_station AS paths\n" +
                        "FROM bj_subway\n" +
                        "WHERE station_name = ?\n" +
                        "UNION ALL \n" +
                        "SELECT t.start_station, s.next_station, stops+1, paths||'->'||s.line_name||s.next_station\n" +
                        "FROM transfer t\n" +
                        "JOIN bj_subway s \n" +
                        "ON (t.stop_station = s.station_name AND instr(paths, s.next_station)=0)\n" +
                        ")\n" +
                        "SELECT *\n" +
                        "FROM transfer\n" +
                        "WHERE stop_station = ?;";

        Cursor cursor = db.rawQuery(sql,new String[]{station1,station2});
        SubwayBean subwayBean = new SubwayBean();
        if (cursor.moveToFirst()){
            subwayBean._StartStation = cursor.getString(cursor.getColumnIndex("start_station"));
            subwayBean._EndStation = cursor.getString(cursor.getColumnIndex("stop_station"));
            subwayBean._Number = cursor.getString(cursor.getColumnIndex("stops"));
            subwayBean._Path = cursor.getString(cursor.getColumnIndex("paths"));
        }
        cursor.close();
        db.close();
        return  subwayBean;
    }

}