最终效果图如下:
还是图、邻接表,可以模拟出几个对象=》节点、边、路径。三个类分别如下:
Node 节点:
using System;
using System.Collections.Generic;
namespace Road.Plan
{
public class Node
{
private string id;
private IList edgeList;
public double Lat
{
get;
set;
}
public double Lng
{
get;
set;
}
public Node(string nid)
{
id = nid;
edgeList = new List();
}
public string Id
{
get
{
return id;
}
}
public IList EdgeList
{
get
{
return edgeList;
}
}
}
}
Edge 边:
using System;
using System.Web.Script.Serialization;
namespace Road.Plan
{
public class Edge
{
[ScriptIgnore]
public Node StartNode
{
get;
set;
}
[ScriptIgnore]
public Node EndNode
{
get;
set;
}
public int Weight
{
get;
set;
}
}
}
Graph 图:
using System;
using System.Collections.Generic;
namespace Road.Plan
{
///
/// 由于边存在节点里了,邻接表的方式的图就这么简单
///
public class Graph
{
public List NodeList = new List();
}
}
路径Path:
using System;
using System.Collections.Generic;
namespace Road.Plan
{
public class Path
{
//起始点 到 这个点
public string CurrentNodeId;
//该点是否已经计算
public bool IsProcessed = false;
//路径 权重合计
public int Weight = 99999999;
//路径表示
public List PathNodeList = new List();
}
}
路径规划辅助类:
using System; using System.Collections.Generic; using System.Linq; namespace Road.Plan { /// /// 计算最短路径帮助类 /// public class CaculateHelper { private Dictionary<string, Path> dicPath = new Dictionary<string, Path>(); public Dictionary<string, Path> DicPath { get { return dicPath; } } public void IniFirstNode(Graph graph, string StartNodeId) { Node OriginNode = null; foreach (Node node in graph.NodeList) { if (node.Id == StartNodeId) { OriginNode = node; } else { Path path = new Path(); path.CurrentNodeId = node.Id; dicPath.Add(path.CurrentNodeId, path); //初始化A->到所有边都是默认的Path 99999999 } } //如果有A直接进入的边,则设置为相应权重值,和记录下路径 foreach (Edge edge in OriginNode.EdgeList) { Path path = new Path(); path.CurrentNodeId = edge.EndNode.Id; path.Weight = edge.Weight; path.PathNodeList.Add(edge.StartNode); dicPath[path.CurrentNodeId] = path; } } public Node GetFromNodeMinWeightNode(Graph graph) { Node CNode = null; KeyValuePair<string, Path> KVPPath = dicPath.Where(m => !m.Value.IsProcessed).OrderBy(m => m.Value.Weight).FirstOrDefault(); if (KVPPath.Key != null) { CNode = graph.NodeList.FirstOrDefault(m => m.Id == KVPPath.Value.CurrentNodeId); } return CNode; } /// /// 计算最短权值路径 /// public void CatelateMinWeightRoad(Graph graph, string StartNodeId) { //取从第一个点出发,最小权值且未被访问果的节点的点 Node CNode = GetFromNodeMinWeightNode(graph); //这段代码是核心 循环每个顶点,看看经过该顶点是否会让权值变小,如果会则存起此路径。直到再未访问过的点 while (CNode != null) { Path CurrentPath = dicPath[CNode.Id]; foreach (Edge edge in CNode.EdgeList) { if (edge.EndNode.Id == StartNodeId) { continue; } Path TargetPath = dicPath[edge.EndNode.Id]; int tempWeight = CurrentPath.Weight + edge.Weight; if (tempWeight < TargetPath.Weight) { TargetPath.Weight = tempWeight; TargetPath.PathNodeList.Clear(); for (int i = 0; i < CurrentPath.PathNodeList.Count; i++) { TargetPath.PathNodeList.Add(CurrentPath.PathNodeList[i]); } TargetPath.PathNodeList.Add(CNode); } } //标志为已处理 dicPath[CNode.Id].IsProcessed = true; //再次获取权值最小的点 CNode = GetFromNodeMinWeightNode(graph); } } } }
此处需要1个Controller、3个Action、1个页面。
第一步,打开地图、并初始化好”运算-图”。
第二步,获取所有节点,并将节点在地图上显示出来。
第三步,获取运算结果,并在地图上根据计算结果将线划出来。
Controller代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using Road.Plan;
namespace Road.Controllers
{
public class HomeController : Controller
{
static Graph graph = new Graph();
public ActionResult GetAllNodes()
{
return Json(graph.NodeList, JsonRequestBehavior.AllowGet);
}
public ActionResult Index()
{
graph.NodeList.Clear();
#region 初始化航路-图
Node Node1 = new Node("1");
Node1.Lat = 23.1589850342836;
Node1.Lng = 112.7859878540039;
graph.NodeList.Add(Node1);
Node Node2 = new Node("2");
Node2.Lat = 23.136255816129122;
Node2.Lng = 112.79937744140625;
graph.NodeList.Add(Node2);
Node Node3 = new Node("3");
Node3.Lat = 23.11447003284563;
Node3.Lng = 112.79869079589844;
graph.NodeList.Add(Node3);
Node Node4 = new Node("4");
Node4.Lat = 23.142885569598484;
Node4.Lng = 112.80890464782715;
graph.NodeList.Add(Node4);
Node Node5 = new Node("5");
Node5.Lat = 23.144621879424374;
Node5.Lng = 112.81577110290527;
graph.NodeList.Add(Node5);
Node Node6 = new Node("6");
Node6.Lat = 23.151566893799817;
Node6.Lng = 112.82074928283691;
graph.NodeList.Add(Node6);
Node Node7 = new Node("7");
Node7.Lat = 23.15551276434145;
Node7.Lng = 112.82984733581543;
graph.NodeList.Add(Node7);
Node Node8 = new Node("8");
Node8.Lat = 23.1545657660099;
Node8.Lng = 112.84452438354492;
graph.NodeList.Add(Node8);
Node Node9 = new Node("9");
Node9.Lat = 23.167507497056675;
Node9.Lng = 112.81705856323242;
graph.NodeList.Add(Node9);
//***************** 1 Node *******************
//1 -> 2
Edge aEdge1 = new Edge();
aEdge1.StartNode = Node1;
aEdge1.EndNode = Node2;
aEdge1.Weight = 1;
Node1.EdgeList.Add(aEdge1);
//***************** 2 Node *******************
//2 -> 3
Edge bEdge3 = new Edge();
bEdge3.StartNode = Node2;
bEdge3.EndNode = Node3;
bEdge3.Weight = 1;
Node2.EdgeList.Add(bEdge3);
//2 -> 1
Edge bEdge1 = new Edge();
bEdge1.StartNode = Node2;
bEdge1.EndNode = Node1;
bEdge1.Weight = 1;
Node2.EdgeList.Add(bEdge1);
//2 -> 4
Edge bEdge4 = new Edge();
bEdge4.StartNode = Node2;
bEdge4.EndNode = Node4;
bEdge4.Weight = 1;
Node2.EdgeList.Add(bEdge4);
//***************** 3 Node *******************
//3 -> 2
Edge cEdge2 = new Edge();
cEdge2.StartNode = Node3;
cEdge2.EndNode = Node2;
cEdge2.Weight = 1;
Node3.EdgeList.Add(cEdge2);
//***************** 4 Node *******************
//4 -> 2
Edge dEdge2 = new Edge();
dEdge2.StartNode = Node4;
dEdge2.EndNode = Node2;
dEdge2.Weight = 1;
Node4.EdgeList.Add(dEdge2);
//4 -> 5
Edge dEdge5 = new Edge();
dEdge5.StartNode = Node4;
dEdge5.EndNode = Node5;
dEdge5.Weight = 1;
Node4.EdgeList.Add(dEdge5);
//***************** 5 Node *******************
//5 -> 6
Edge eEdge6 = new Edge();
eEdge6.StartNode = Node5;
eEdge6.EndNode = Node6;
eEdge6.Weight = 1;
Node5.EdgeList.Add(eEdge6);
//5 -> 4
Edge eEdge4 = new Edge();
eEdge4.StartNode = Node5;
eEdge4.EndNode = Node4;
eEdge4.Weight = 1;
Node5.EdgeList.Add(eEdge4);
//***************** 6 Node *******************
//6 -> 5
Edge fEdge5 = new Edge();
fEdge5.StartNode = Node6;
fEdge5.EndNode = Node5;
fEdge5.Weight = 1;
Node6.EdgeList.Add(fEdge5);
//6 -> 7
Edge fEdge7 = new Edge();
fEdge7.StartNode = Node6;
fEdge7.EndNode = Node7;
fEdge7.Weight = 1;
Node6.EdgeList.Add(fEdge7);
//***************** 7 Node *******************
//7 -> 6
Edge gEdge6 = new Edge();
gEdge6.StartNode = Node7;
gEdge6.EndNode = Node6;
gEdge6.Weight = 1;
Node7.EdgeList.Add(gEdge6);
//7 -> 8
Edge gEdge8 = new Edge();
gEdge8.StartNode = Node7;
gEdge8.EndNode = Node8;
gEdge8.Weight = 1;
Node7.EdgeList.Add(gEdge8);
//7 -> 9
Edge gEdge9 = new Edge();
gEdge9.StartNode = Node7;
gEdge9.EndNode = Node9;
gEdge9.Weight = 1;
Node7.EdgeList.Add(gEdge9);
//***************** 8 Node *******************
//8 -> 7
Edge hEdge7 = new Edge();
hEdge7.StartNode = Node8;
hEdge7.EndNode = Node7;
hEdge7.Weight = 1;
Node8.EdgeList.Add(hEdge7);
//***************** 9 Node *******************
//9 -> 7
Edge iEdge7 = new Edge();
iEdge7.StartNode = Node9;
iEdge7.EndNode = Node7;
iEdge7.Weight = 1;
Node9.EdgeList.Add(iEdge7);
#endregion
return View();
}
///
/// 计算起始点,结束点的最短路径
///
///
///
///
public ActionResult GetWaterWay(string StartNodeId, string EndNodeId)
{
CaculateHelper CH = new CaculateHelper();
//第一步,初始化初始化源点 A 到 其他各点的 权重以及 路径(完成 A->B A->C A->E A->D 边权重,与A无直接边的则默认99999999)
CH.IniFirstNode(graph, StartNodeId);
//第二步,从权重最小的点开始,一直到权值最大的点
CH.CatelateMinWeightRoad(graph, StartNodeId);
//组合返回值
Path ShowPath = CH.DicPath[EndNodeId];
ShowPath.PathNodeList.Add(graph.NodeList.First(m => m.Id == EndNodeId)); //补上结束点
return Json(ShowPath.PathNodeList);
}
}
}
页面HTML代码如下:
DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no">
<meta charset="utf-8">
<title>Complex iconstitle>
<style>
html, body, #map-canvas {
height: 100%;
margin: 0px;
padding: 0px;
}
style>
<script src="/jquery-1.10.2.min.js">script>
<script src="http://ditu.google.cn/maps/api/js?sensor=false" type="text/javascript">script>
<script>
var map;
var lat = 23.144621879424374;
var lng = 112.81577110290527;
var myLatlng = new google.maps.LatLng(lat, lng);
//添加一个标记
function addMarker(lat, lng, title) {
var LatLng = new google.maps.LatLng(lat, lng);
var marker = new google.maps.Marker({
map: map,
position: LatLng,
title: title
});
return marker;
}
function LatLng(lat, lng) {
return {
lat: lat,
lng: lng
};
}
//线条选项
function lineOption() {
var lineOption = {
strokeColor: "#FF0000",
strokeOpacity: 1.0,
strokeWeight: 2,
coordinates: []
};
return lineOption;
}
//画线
function addLine(lineOption) {
var linecoordinates = [];
for (var i = 0; i < lineOption.coordinates.length; i++) {
linecoordinates.push(new google.maps.LatLng(lineOption.coordinates[i].lat, lineOption.coordinates[i].lng));
}
//显示线
var line = new google.maps.Polyline({
path: linecoordinates,
strokeColor: lineOption.strokeColor,
strokeOpacity: lineOption.strokeOpacity,
strokeWeight: lineOption.strokeWeight,
map: map
});
return line;
}
var MarkerId = 1;
//初始化谷歌地图
function initialize() {
//设置地图中心
var mapOptions = {
zoom: 12,
center: myLatlng
}
map = new google.maps.Map(document.getElementById('map-canvas'), mapOptions);
//google.maps.event.addListener(map, 'click', function (e) {
// var str = $("#position").html();
// var MID = MarkerId++;
// addMarker(e.latLng.lat(), e.latLng.lng(), MID);
// $("#position").html(str + " " + MID + " " + e.latLng.lat() + " " + e.latLng.lng() + "
");
//});
$.ajax({
url: "/Home/GetAllNodes",
dataType: "json",
type: "post",
success: function (data) {
for (var i = 0; i < data.length; i++)
{
addMarker(data[i].Lat, data[i].Lng, data[i].Id);
}
}
})
$.ajax({
url: "/Home/GetWaterWay",
dataType: "json",
type: "post",
data:{
StartNodeId: "1",
EndNodeId: "9"
},
success: function (data) {
var lo = lineOption();
lo.strokeWeight = 4;
lo.strokeColor = "Green";
lo.strokeOpacity = 0.8;
//用返回的路线画线
for (var i = 0; i < data.length; i++)
{
lo.coordinates.push(LatLng(data[i].Lat, data[i].Lng));
}
addLine(lo);
}
})
}
//监听页面事件,当页面加载完毕,加载谷歌地图
google.maps.event.addDomListener(window, 'load', initialize);
script>
head>
<body>
<div id="map-canvas" style="height:600px;">div>
<div id="position">div>
body>
html>
Original: https://www.cnblogs.com/kissdodog/p/5439217.html
Author: 逆心
Title: 基于谷歌地图的Dijkstra算法水路路径规划
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/552319/
转载文章受原作者版权保护。转载请注明原作者出处!