From 8e3b276ae8638ef8a94d9e3f987482b253823596 Mon Sep 17 00:00:00 2001
From: asmrobot <asmrobot@hotmail.com>
Date: Sun, 03 Nov 2019 16:47:52 +0000
Subject: [PATCH] finish path finding by dijitrla
---
src/test/Program.cs | 640 ++++++++++++++++-----------------------------------------
1 files changed, 182 insertions(+), 458 deletions(-)
diff --git a/src/test/Program.cs b/src/test/Program.cs
index a943b0e..5131453 100644
--- a/src/test/Program.cs
+++ b/src/test/Program.cs
@@ -5,486 +5,210 @@
using System.Threading.Tasks;
using System.Threading;
using System.Drawing;
-using static test.Graphics;
+using System.Reflection.Emit;
+using System.Reflection;
namespace test
{
-
-
- public struct person
+ public class Dijkstra<T> where T:IEquatable<T>
{
- public int age { get; set; }
+ private Dictionary<T, Dictionary<T, int>> vertices = new Dictionary<T, Dictionary<T, int>>();
- public string name { get; set; }
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="edges">顶点所有的边</param>
+ public void AddVertex(T name, Dictionary<T, int> edges)
+ {
+ foreach (var item in edges)
+ {
+ AddVertex(name, item.Key, item.Value);
+ }
+ }
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="target">可连接顶点</param>
+ /// <param name="weight">权重</param>
+ public void AddVertex(T name, T target, int weight)
+ {
+ if (!this.vertices.ContainsKey(name))
+ {
+ this.vertices.Add(name, new Dictionary<T, int>());
+ }
+
+ if (this.vertices[name].ContainsKey(target))
+ {
+ return;
+ }
+
+ this.vertices[name].Add(target, weight);
+ }
+
+ /// <summary>
+ /// 移除顶点
+ /// </summary>
+ /// <param name="name"></param>
+ public void RemoveVertex(T name)
+ {
+ if (this.vertices.ContainsKey(name))
+ {
+ return;
+ }
+ this.vertices.Remove(name);
+ foreach (var item in this.vertices)
+ {
+ if (item.Value.ContainsKey(name))
+ {
+ item.Value.Remove(name);
+ }
+ }
+ }
+
+
+
+
+ /// <summary>
+ /// 查找最短路径
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="finish"></param>
+ /// <returns></returns>
+
+ public List<T> ShortestPath(T start, T finish)
+ {
+ var previous = new Dictionary<T, T>();
+ var distances = new Dictionary<T, int>();
+ var nodes = new List<T>();
+
+ List<T> path = null;
+
+ foreach (var vertex in vertices)
+ {
+ if (vertex.Key .Equals( start))
+ {
+ distances[vertex.Key] = 0;
+ }
+ else
+ {
+ distances[vertex.Key] = int.MaxValue;
+ }
+
+ nodes.Add(vertex.Key);
+ }
+
+ while (nodes.Count != 0)
+ {
+ nodes.Sort((x, y) => distances[x] - distances[y]);
+
+ var smallest = nodes[0];
+ nodes.Remove(smallest);
+
+ if (smallest .Equals( finish))
+ {
+ path = new List<T>();
+ while (previous.ContainsKey(smallest))
+ {
+ path.Add(smallest);
+ smallest = previous[smallest];
+ }
+
+ break;
+ }
+
+ if (distances[smallest] == int.MaxValue)
+ {
+ break;
+ }
+
+ foreach (var neighbor in vertices[smallest])
+ {
+ var alt = distances[smallest] + neighbor.Value;
+ if (alt < distances[neighbor.Key])
+ {
+ distances[neighbor.Key] = alt;
+ previous[neighbor.Key] = smallest;
+ }
+ }
+ }
+
+ return path;
+ }
}
+
+ public struct person:IEquatable<person>
+ {
+ public person(Int32 age,string name)
+ {
+ this.Age = age;
+ this.Name = name;
+ }
+ public int Age { get; set; }
+
+ public string Name { get; set; }
+
+ public bool Equals(person other)
+ {
+ if (this.Age == other.Age && Name.Equals(other.Name, StringComparison.Ordinal))
+ {
+ return true;
+ }
+ return false;
+ }
+
+ public override int GetHashCode()
+ {
+ Int32 hashcode = 17;
+ hashcode = hashcode * 23 + this.Age.GetHashCode();
+ hashcode = hashcode * 23 + this.Name.GetHashCode();
+ return hashcode;
+ }
+
+ public override string ToString()
+ {
+ return this.Name + "," + this.Age.ToString();
+ }
+
+
+
+ }
class Program
{
-
- //static void GetN(person p)
- //{
- // p = new person();
- // p.age = 2;
- //}
-
+
static void Main(string[] args)
{
+ person a = new person(235, "a0");
+ person b = new person(12, "b1");
+ person c = new person(34, "c2");
+ person d = new person(45, "d3");
+ person e = new person(56, "e4");
+ Dijkstra<person> dij = new Dijkstra<person>();
+ dij.AddVertex(a, new Dictionary<person, int>() { { b, 7 }, { d, 8 } });
+ dij.AddVertex(b, new Dictionary<person, int>() { { a, 7 }, { c, 2 },{ d,2} ,{ e,3} });
+ dij.AddVertex(c, new Dictionary<person, int>() { { b, 8 }, { e, 6 } });
+ dij.AddVertex(d, new Dictionary<person, int>() { { a, 8 },{ b,2} });
+ dij.AddVertex(e, new Dictionary<person, int>() { { b, 1 },{ c,2} });
+ dij.ShortestPath(d, e).ForEach(x => Console.WriteLine(x));
+ ZTImage.Diagnostics.CodeTimer.Timer("dij", 10000, () =>
+ {
+ //g.ShortestPath('A', 'H').ForEach(x => Console.WriteLine(x));
+ dij.ShortestPath(a, b);
- person p = new person();
- p.age = 12;
- p.name = "xylee";
-
-
- Console.WriteLine(ZTImage.Json.JsonBuilder.ToJsonString(p));
+ });
- //ZTPoint A = new ZTPoint(0, 1);
- //ZTPoint B = new ZTPoint(1, 0);
- //ZTPoint C = new ZTPoint(3, 0);
- //ZTPoint D = new ZTPoint(4, 1);
- //ZTPoint E = new ZTPoint(3, 2);
- //ZTPoint F = new ZTPoint(2, 1);
- //ZTPoint G = new ZTPoint(1, 2);
- //var edges = new List<Tuple<ZTPoint, ZTPoint, double>>()
- //{
- // new Tuple<ZTPoint,ZTPoint,double>(A,B,12),
- // new Tuple<ZTPoint,ZTPoint,double>(A,F,16),
- // new Tuple<ZTPoint,ZTPoint,double>(A,G,14),
- // new Tuple<ZTPoint,ZTPoint,double>(B,F,7),
- // new Tuple<ZTPoint,ZTPoint,double>(B,C,10),
- // new Tuple<ZTPoint,ZTPoint,double>(G,F,9),
- // new Tuple<ZTPoint,ZTPoint,double>(G,E,8),
- // new Tuple<ZTPoint,ZTPoint,double>(F,C,6),
- // new Tuple<ZTPoint,ZTPoint,double>(F,E,2),
- // new Tuple<ZTPoint,ZTPoint,double>(C,D,3),
- // new Tuple<ZTPoint,ZTPoint,double>(C,E,5),
- // new Tuple<ZTPoint,ZTPoint,double>(E,D,4),
- //};
-
- //var dij = new Dijkstra(edges);
- //var path = dij.Find(D, G);
-
- //for (int i = 0; i < path.Count; i++)
- //{
- // Console.WriteLine(path[i].ToString());
- //}
-
-
- Console.WriteLine("finish!~");
Console.ReadKey();
}
+
}
-
-
- /// <summary>
- /// 图
- /// </summary>
- public class Graphics
- {
- public const int MaxSize = 6;
- public const int INF = 32767; //INF表示∞
- public const int MAXV = 4; //最大顶点个数
- //结构体的成员定义里不能直接赋值，也就是等号后的应该移除，在你后面实例化整个结构体以后，
- //再对Study_Data[n].input=new double[50] 其他成员类似。顺便说下其实用class简单得多。
-
- public struct VertexType
- {
- public string VexNo; //顶点编号
- public string VexName; //顶点名称
- public string otherInfo; //顶点其他信息
- }; //顶点类型
- public struct MGraph //图的定义
- {
- public int[,] edges; //邻接矩阵
- public int n, e; //顶点数,弧数
- public VertexType[] vexs; //存放顶点信息
- }; //图的邻接矩阵类型
-
- static void Ppath(int[] path, int i, int v) //前向递归查找路径上的顶点
- {
- int k;
- k = path[i];
- if (k == v) return; //找到了起点则返回
- Ppath(path, k, v); //找顶点k的前一个顶点v
-
- Console.Write("{0},", k); //输出路径上的终点
- // Ppath(path, k, j); //找顶点k的前一个顶点j
- }
-
- static void Ppath(MGraph g, int[] path, int i, int v) //前向递归查找路径上的顶点
- {
- int k;
- k = path[i];
- if (k == v) return; //找到了起点则返回
- Ppath(path, k, v); //找顶点k的前一个顶点v
-
- Console.Write("{0},", g.vexs[k].VexName); //输出路径上的终点
- // Ppath(path, k, j); //找顶点k的前一个顶点j
- }
-
- static void Dispath(int[] dist, int[] path, int[] s, int n, int v)
- {
- int i;
- for (i = 0; i < n; i++)
- {
- if (s[i] == 1)
- {
- Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
- Console.Write("{0},", v); //输出路径上的起点
- Ppath(path, i, v); //输出路径上的中间点
- Console.WriteLine("{0}", i); //输出路径上的终点
- }
- else
- Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
- }
- }
-
- static void PutBothpath(MGraph g, int[] dist, int[] path, int[] s, int n, int v, int m)
- {
- int i;
- for (i = 0; i < n; i++)
- {
- if (s[i] == 1)
- {
- //Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
- //Console.Write("{0},", v); //输出路径上的起点
- //Ppath(path, i, v); //输出路径上的中间点
- //Console.WriteLine("{0}", i); //输出路径上的终点
- if (i == m && dist[i] < INF)
- {
- Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", g.vexs[v].VexName, g.vexs[i].VexName, dist[i]);
- Console.Write("{0},", g.vexs[v].VexName); //输出路径上的起点
- //Ppath(path, i, v); //输出路径上的中间点
- Ppath(g, path, i, v);
- Console.WriteLine("{0}", g.vexs[i].VexName); //输出路径上的终点
- }
- }
- else
- Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
- }
- }
-
- public static void Dijkstra(MGraph g, int v)
- {
- int[] dist = new int[MAXV];//从原点v到其他的各定点当前的最短路径长度
- int[] path = new int[MAXV];//path[i]表示从原点到定点i之间最短路径的前驱节点
- int[] s = new int[MAXV]; //选定的顶点的集合
- int mindis, i, j, u;
- u = 0;
- for (i = 0; i < g.n; i++)
- {
- dist[i] = g.edges[v, i]; //距离初始化
- s[i] = 0; //s[]置空 0表示i不在s集合中
- if (g.edges[v, i] < INF) //路径初始化
- path[i] = v;
- else
- path[i] = -1;
- }
- s[v] = 1; //源点编号v放入s中
- path[v] = 0;
- for (i = 0; i < g.n; i++) //循环直到所有顶点的最短路径都求出
- {
- mindis = INF; //mindis置最小长度初值
- for (j = 0; j < g.n; j++) //选取不在s中且具有最小距离的顶点u
- if (s[j] == 0 && dist[j] < mindis)
- {
- u = j;
- mindis = dist[j];
- }
- s[u] = 1; //顶点u加入s中
- for (j = 0; j < g.n; j++) //修改不在s中的顶点的距离
- if (s[j] == 0)
- if (g.edges[u, j] < INF && dist[u] + g.edges[u, j] < dist[j])
- {
- dist[j] = dist[u] + g.edges[u, j];
- path[j] = u;
- }
- }
- Dispath(dist, path, s, g.n, v); //输出最短路径
- //PutBothpath(g, dist, path, s, g.n, v, 3);
- }
-
- static void initdata()
- {
- int i, j;
- MGraph g;
- g.n = 4; g.e = 8;
- g.edges = new int[MAXV, MAXV];
- g.vexs = new VertexType[MAXV];
- //int [,] anArray = new int [2, 4] {{1,2,3,4},{5,6,7,8}};
- int[,] a = new int[MAXV, MAXV] {
- {0, 5,INF,7},
- {INF,0, 4,2},
- {3, 3, 0,2},
- {INF,INF,1,0}
- };
-
- for (i = 0; i < g.n; i++) //建立图的图的邻接矩阵
- {
- for (j = 0; j < g.n; j++)
- {
- g.edges[i, j] = a[i, j];///////////////////////////////////////////////
- }
- }
- Console.WriteLine("各顶点的最短路径:");
- }
-
- public static void initialVexInfo(MGraph g)
- {
- g.vexs[0].VexNo = "0361";
- g.vexs[0].VexName = "西安";
-
- g.vexs[1].VexNo = "010";
- g.vexs[1].VexName = "北京";
-
- g.vexs[2].VexNo = "0681";
- g.vexs[2].VexName = "武汉";
-
- g.vexs[3].VexNo = "0571";
- g.vexs[3].VexName = "杭州";
- }
- }
-
-
- //public class StationSched
- //{
- // /// <summary>
- // /// 所有的站点信息
- // /// </summary>
- // List<StationInfo> stations = new List<StationInfo>();
-
- // /// <summary>
- // /// 线路信息
- // /// </summary>
- // List<ShipInfo> lines = new List<ShipInfo>();
-
- // /// <summary>
- // /// 构造函数，初始化站点和线路信息
- // /// </summary>
- // public StationSched()
- // {
- // stations.Add(new StationInfo() { Sid = 1, Lid = 1 });//0
- // stations.Add(new StationInfo() { Sid = 2, Lid = 1 });//1
- // stations.Add(new StationInfo() { Sid = 3, Lid = 1 });//2
- // stations.Add(new StationInfo() { Sid = 4, Lid = 1 });//3
- // stations.Add(new StationInfo() { Sid = 5, Lid = 1 });//4
- // stations.Add(new StationInfo() { Sid = 6, Lid = 1 });//5
- // stations.Add(new StationInfo() { Sid = 7, Lid = 1 });//6
-
- // stations.Add(new StationInfo() { Sid = 19, Lid = 2 });//7
- // stations.Add(new StationInfo() { Sid = 18, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 17, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 3, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 13, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 16, Lid = 2 });
-
-
- // stations.Add(new StationInfo() { Sid = 15, Lid = 3 });//13
- // stations.Add(new StationInfo() { Sid = 14, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 13, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 12, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 11, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 5, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 10, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 9, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 8, Lid = 3 });
-
- // for (int i = 0; i < 6; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 6; i > 0; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // for (int i = 7; i < 12; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 12; i > 7; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // for (int i = 13; i < 21; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 21; i > 13; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // }
-
- // /// <summary>
- // /// 获取sid站点可以到达的站点信息，去除已经计算过的preid站点
- // /// </summary>
- // /// <param name="preid"></param>
- // /// <param name="sid"></param>
- // /// <returns></returns>
- // public List<StationInfo> GetNext(int preid, int sid)
- // {
- // List<StationInfo> list = new List<StationInfo>();
- // foreach (var item in lines)
- // {
- // if (item.Curr.Sid == sid && item.Next.Sid != preid) list.Add(item.Next);
- // }
- // return list;
- // }
-
- // /// <summary>
- // /// 获取线路信息
- // /// </summary>
- // /// <param name="s">起始站点编号</param>
- // /// <param name="e">结束站点编号</param>
- // /// <returns></returns>
- // public List<string> GetResult(int s, int e)
- // {
- // List<List<int>> temp = GetLine(s, e);
- // List<string> result = new List<string>();
- // List<List<int>> line = new List<List<int>>();
- // foreach (var item in temp)
- // {
- // if (item.Count > 0 && item[item.Count - 1] == e)
- // line.Add(item);
- // }
- // string src = "";
- // int currLine = -1;
- // foreach (var item in line)
- // {
- // currLine = GetLineNumber(item[0], item[1]);
- // src += "从[" + currLine + "号线]的[" + item[0] + "]上车";
- // for (int i = 1; i < item.Count; i++)
- // {
- // if (i == item.Count - 1)
- // {
- // src += ",在[" + item[i] + "]站点下车。";
- // result.Add(src);
- // src = "";
- // break;
- // }
- // int tempLine = GetLineNumber(item[i], item[i + 1]);
- // if (tempLine != currLine)
- // {
- // currLine = tempLine;
- // src += ",在[" + item[i] + "]站点换乘[" + currLine + "号线]";
- // }
- // }
-
- // }
-
- // return result;
- // }
-
- // /// <summary>
- // /// 根据相邻的两个点取当前的线路
- // /// </summary>
- // /// <param name="s"></param>
- // /// <param name="e"></param>
- // /// <returns></returns>
- // private int GetLineNumber(int l, int r)
- // {
- // foreach (var item in lines)
- // {
- // if ((item.Curr.Sid == l && item.Next.Sid == r) || (item.Curr.Sid == r && item.Next.Sid == l))
- // return item.Next.Lid;
- // }
- // return -1;
- // }
-
- // /// <summary>
- // /// 获取线路的ID集合
- // /// </summary>
- // /// <param name="s">起始站点编号</param>
- // /// <param name="e">结束站点编号</param>
- // /// <returns></returns>
- // private List<List<int>> GetLine(int s, int e)
- // {
- // List<List<int>> result = new List<List<int>>();
- // List<int> curr = new List<int>();
- // curr.Add(s);
- // result.Add(curr);
- // int currLine = 0;
- // int preSid = s;
- // int currSid = s;
- // while (true)
- // {
- // if (currLine >= result.Count) return result;
- // currSid = result[currLine][result[currLine].Count - 1];
- // if (currSid == e)
- // {
- // currLine += 1;
- // continue;
- // }
- // if (result[currLine].Count > 1)
- // preSid = result[currLine][result[currLine].Count - 2];
- // if (currSid <= 0)
- // {
- // currLine += 1;
- // continue;
- // }
- // List<StationInfo> temp = GetNext(preSid, currSid);
-
- // if (temp.Count == 0)
- // {//某条线路到头
- // currLine += 1;
- // }
- // else if (temp.Count == 1)
- // {//不需要换乘继续前进
- // result[currLine].Add(temp[0].Sid);
- // }
- // else
- // {//需要换乘了。
- // for (int i = 1; i < temp.Count; i++)
- // {
- // if (!result[currLine].Contains(temp[i].Sid))
- // {//防止死循环，过滤掉已经计算过的站点。
- // result.Add(result[currLine].GetRange(0, result[currLine].Count));
- // result[result.Count - 1].Add(temp[i].Sid);
- // }
- // }
- // result[currLine].Add(temp[0].Sid);
- // }
- // }
- // }
- //}
-
-
-
- ///// <summary>
- ///// 站点信息
- ///// </summary>
- //public class StationInfo
- //{
- // public int Lid { get; set; }
- // public int Sid { get; set; }
-
- // public override string ToString()
- // {
- // return "Sid:" + Sid + "--Lid:" + Lid;
- // }
- //}
-
- ///// <summary>
- ///// 关系信息
- ///// </summary>
- //public class ShipInfo
- //{
- // public StationInfo Curr { get; set; }
- // public StationInfo Next { get; set; }
-
- // public override string ToString()
- // {
- // return "Curr:" + Curr.Sid + "--Next:" + Next.Sid;
- // }
- //}
}
--
Gitblit v1.9.3