You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
261 lines
11 KiB
261 lines
11 KiB
using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using UnityEngine;
|
|
using ARLocation;
|
|
|
|
public class dijkstraShortPathInfo : MonoBehaviour
|
|
{
|
|
public LocationPath locationPath;
|
|
//public Location[] locations;
|
|
// Start is called before the first frame update
|
|
public void GetPath(int x, int y){
|
|
dijkstra(adjacencyMatrix, x, y);
|
|
Array.Resize(ref locationPath.Locations, savepath.Length);
|
|
Invoke("Fcc", 1f);
|
|
}
|
|
void Fcc()
|
|
{
|
|
for (int i = 0; i < savepath.Length; i++)
|
|
{
|
|
locationPath.Locations[i].Latitude = xx[savepath[i]];
|
|
locationPath.Locations[i].Longitude = yy[savepath[i]];
|
|
}
|
|
}
|
|
private void Start()
|
|
{
|
|
Array.Resize(ref locationPath.Locations, 0);
|
|
}
|
|
public static double[] xx = {35.968340,
|
|
35.968344,
|
|
35.967567,
|
|
35.967233,
|
|
35.967175,
|
|
35.967116,
|
|
35.967376,
|
|
35.967466,
|
|
35.967796,
|
|
35.968186,
|
|
35.968294,
|
|
35.968169,
|
|
35.968122,
|
|
35.967498,
|
|
35.968656,
|
|
35.968681,
|
|
35.968701,
|
|
35.968712,
|
|
35.968747,
|
|
35.968811,
|
|
35.969017,
|
|
35.969254,
|
|
35.969649,
|
|
35.970050,
|
|
35.970448,
|
|
35.970412,
|
|
35.970105,
|
|
35.970123,
|
|
35.970074,
|
|
35.970277,
|
|
35.970773,
|
|
35.971093,
|
|
35.971691,
|
|
35.972213,
|
|
35.971945,
|
|
35.968735,
|
|
35.969062,
|
|
35.969360,
|
|
35.969972,
|
|
35.969965,
|
|
35.970113,
|
|
35.969409,
|
|
35.969063,
|
|
35.969110};
|
|
|
|
public static double[] yy = {126.958104,
|
|
126.958931,
|
|
126.959010,
|
|
126.959057,
|
|
126.958213,
|
|
126.957411,
|
|
126.957384,
|
|
126.958192,
|
|
126.957333,
|
|
126.957295,
|
|
126.957481,
|
|
126.957026,
|
|
126.956660,
|
|
126.956364,
|
|
126.956969,
|
|
126.958065,
|
|
126.958890,
|
|
126.959303,
|
|
126.960234,
|
|
126.960767,
|
|
126.959285,
|
|
126.959269,
|
|
126.959206,
|
|
126.959107,
|
|
126.959044,
|
|
126.958577,
|
|
126.958505,
|
|
126.958834,
|
|
126.958083,
|
|
126.958161,
|
|
126.958137,
|
|
126.958119,
|
|
126.958135,
|
|
126.958130,
|
|
126.957231,
|
|
126.956853,
|
|
126.956823,
|
|
126.956825,
|
|
126.956810,
|
|
126.955791,
|
|
126.955241,
|
|
126.955928,
|
|
126.956008,
|
|
126.956427};
|
|
|
|
private static readonly int NO_PARENT = -1;
|
|
|
|
//경로 저장 배열
|
|
public static int[] savepath;
|
|
|
|
public static int[,] adjacencyMatrix = {{0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{1,0,1,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{1,2,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1},
|
|
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0}};
|
|
|
|
|
|
public static void dijkstra(int[,] adjacencyMatrix, int startVertex, int destinationvertex)
|
|
{
|
|
int nVertices = adjacencyMatrix.GetLength(0);
|
|
|
|
//shortestDistances[i]는 src(출발지)에서 i까지의 최단 거리를 유지합니다
|
|
int[] shortestDistances = new int[nVertices];
|
|
|
|
//added [i]는 버텍스(vertex정점,노드) i가 포함되어 있거나 최단 경로 트리에 있거나 src에서 i까지의 최단 거리가 완료되면 true입니다.
|
|
bool[] added = new bool[nVertices];
|
|
|
|
//모든 거리를 INFINITE로 초기화하고[]를 false로 추가
|
|
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++)
|
|
{
|
|
shortestDistances[vertexIndex] = int.MaxValue;
|
|
added[vertexIndex] = false;
|
|
}
|
|
|
|
//자체 정점의 거리는 항상 0입니다
|
|
shortestDistances[startVertex] = 0;
|
|
|
|
//최단 경로 트리를 저장하는 부모 배열
|
|
int[] parents = new int[nVertices];
|
|
|
|
//시작 정점에는 부모가 없습니다
|
|
parents[startVertex] = NO_PARENT;
|
|
|
|
//모든 정점에 대한 최단 경로 찾기
|
|
for (int i = 1; i < nVertices; i++)
|
|
{
|
|
//아직 처리되지 않은 정점 세트에서 최소 거리 정점을 지정합니다. 가장 가까운 정점은 첫 번째 반복에서 항상 startNode와 같습니다.
|
|
int nearestVertex = -1;
|
|
int shortestDistance = int.MaxValue;
|
|
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++)
|
|
{
|
|
if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance)
|
|
{
|
|
nearestVertex = vertexIndex;
|
|
shortestDistance = shortestDistances[vertexIndex];
|
|
}
|
|
}
|
|
//선택된 정점을 처리 된 것으로 표시
|
|
added[nearestVertex] = true;
|
|
|
|
//선택된 정점의 인접한 정점의 거리 값을 업데이트합니다.
|
|
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++)
|
|
{
|
|
int edgeDistance = adjacencyMatrix[nearestVertex, vertexIndex];
|
|
if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex]))
|
|
{
|
|
parents[vertexIndex] = nearestVertex;
|
|
shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
|
|
}
|
|
}
|
|
}
|
|
|
|
printSolution(startVertex, shortestDistances, parents, destinationvertex);
|
|
}
|
|
|
|
//구성된 거리 배열과 최단 경로를 인쇄하는 유틸리티 기능
|
|
private static void printSolution(int startVertex, int[] distances, int[] parents, int destinationvertex)
|
|
{
|
|
int nVertices = distances.Length;
|
|
Console.Write("Vertex\t Distance\tPath");
|
|
|
|
//for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++)
|
|
//{
|
|
if (destinationvertex != startVertex)
|
|
{
|
|
Console.Write("\n" + startVertex + " ->");
|
|
Console.Write(destinationvertex + "\t\t");
|
|
Console.Write(distances[destinationvertex] + "\t\t");
|
|
//거리만큼 savepath 배열 크기 재설정
|
|
Array.Resize(ref savepath, distances[destinationvertex] + 1);
|
|
printPath(destinationvertex, parents, distances[destinationvertex] + 1);
|
|
}
|
|
//}
|
|
}
|
|
|
|
//부모 배열을 사용하여 소스에서 currentVertex까지의 최단 경로를 인쇄하는 기능
|
|
private static void printPath(int currentVertex, int[] parents, int chkpoint)
|
|
{
|
|
if (currentVertex == NO_PARENT)
|
|
{
|
|
return;
|
|
}
|
|
printPath(parents[currentVertex], parents, --chkpoint);
|
|
//경로 배열에 저장
|
|
savepath[chkpoint] = currentVertex;
|
|
Console.Write(currentVertex + " ");
|
|
|
|
}
|
|
}
|