使用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; } }