C# 迪杰斯特拉算法 Dijkstra

时间:2022-12-03 22:39:01

什么也不想说,现在直接上封装的方法:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic; namespace 算法
{
/// <summary>
/// Dijkstra
/// 迪杰斯特拉算法
/// </summary>
public class Dijkstra : ICloneable
{ /// <summary>节点集合</summary>
public ConcurrentDictionary<String, Node> LN { get; set; } /// <summary>开始节点</summary>
public Node StartNode { get; set; } /// <summary>结束节点</summary>
public Node EndNode { get; set; } /// <summary>Dijkstra构造函数</summary>
/// <param name="list">节点集合</param>
/// <param name="start">开始节点</param>
/// <param name="end">结束节点</param>
public Dijkstra(ConcurrentDictionary<String, Node> list, String start, String end)
{
LN = list;
Init(start, end);
} /// <summary>Dijkstra构造函数</summary>
/// <param name="list">节点集合</param>
/// <param name="start">开始节点</param>
/// <param name="end">结束节点</param>
public Dijkstra(IEnumerable<Map> list, String start, String end)
{
LN = InitNode(list);
Init(start, end);
} /// <summary>查找最短路径</summary>
public bool Find()
{
return FindMin(new List<Node> { StartNode }, EndNode);
} /// <summary>初始化</summary>
private void Init(String start, String end)
{
StartNode = LN[start];
EndNode = LN[end];
if (StartNode == null || EndNode == null)
{
throw new ArgumentNullException();//空异常
}
StartNode.SetRank(null);
StartNode.IsFind = true; InitRank(new List<Node> { StartNode });
} /// <summary>初始化点阵的Rank </summary>
/// <param name="srcs">节点集合</param>
private void InitRank(IEnumerable<Node> srcs)
{
var nextNode = new List<Node>();
foreach (var node in srcs)
{
foreach (var edge in node.LE)
{
edge.CurrentNode.SetRank(node);
if (edge.CurrentNode.Rank == (node.Rank + 1) && !nextNode.Contains(edge.CurrentNode))
nextNode.Add(edge.CurrentNode);
}
}
if (nextNode.Count > 0) InitRank(nextNode);
} /// <summary>查找</summary>
/// <param name="srcs">开始结点集合</param>
/// <param name="dest">结束节点</param>
private bool FindMin(List<Node> srcs, Node dest)
{
dest.GetRank();
var minLen = 0;
var isFind = false;
var nextNodes = new List<Node>();
string tmpPath;
foreach (var node in srcs)
{
if (node.Equals(dest)) return false;
foreach (var edge in node.LE)
{
var tempDestRank = edge.CurrentNode.Rank;
if (tempDestRank != (node.Rank + 1)) continue; if (!nextNodes.Contains(edge.CurrentNode))
{
nextNodes.Add(edge.CurrentNode);
}
edge.CurrentNode.MinDistance = node.MinDistance + edge.Weight;
if (!edge.CurrentNode.Equals(dest)) continue; minLen = node.MinDistance + edge.Weight;
isFind = true;
break;
}
} if (isFind)
{
foreach (var node in srcs)
{
tmpPath = FindMinx(node, dest, node.MinDistance, node.Rank, "", ref minLen);
if (tmpPath == "") continue;
dest.Path = node.Path + tmpPath;
dest.MinDistance = minLen;
}
}
else
{
foreach (var next in nextNodes)
{
minLen = -1;
foreach (var node in srcs)
{
if (minLen == -1) minLen = next.MinDistance;
tmpPath = FindMinx(node, next, node.MinDistance, node.Rank, "", ref minLen);
if (tmpPath == "") continue;
next.Path = node.Path + tmpPath;
next.MinDistance = minLen;
}
}
if (nextNodes.Count == 0) return false;
FindMin(nextNodes, dest);
} return isFind;
} /// <summary>
/// 寻找起始节点到目标节点的最小路径,此处采用递归查找。目标节点固定,起始节点递归。
/// </summary>
/// <param name="src">起始节点,为临时递归节点</param>
/// <param name="dest">查找路径中的目标节点</param>
/// <param name="minx">当前查找最小路径值,此值在递归*享</param>
/// <param name="startDist">当前节点以src节点的距离</param>
/// <param name="srcRank">源节点src的级别</param>
/// <param name="path">查找中经过的路径</param>
private string FindMinx(Node src, Node dest, int startDist, int srcRank, string path, ref int minx)
{
var goalPath = "";
var tmpPath1 = "," + path + ",";
var tmpPath2 = "," + src.Path + ",";
foreach (var node in src.LE)
{
string tmpPath = path;
node.CurrentNode.SetRank(src);
var tmpRank = node.CurrentNode.Rank;
var tmpNodeName = "," + node.CurrentNode.Name + ",";
//扩散级别大于等于目标级别并且是未走过的节点。
if (tmpRank <= srcRank || tmpPath1.IndexOf(tmpNodeName, StringComparison.Ordinal) != -1 ||
tmpPath2.IndexOf(tmpNodeName, StringComparison.Ordinal) != -1) continue;
var tmpLength = node.Weight + startDist;
if (node.CurrentNode.Equals(dest))
{
if (minx > tmpLength)
{
minx = tmpLength;
tmpPath += "," + node.CurrentNode.Name;
goalPath = tmpPath;
}
else if (minx == tmpLength)
{
tmpPath += "," + node.CurrentNode.Name;
goalPath = tmpPath;
}
}
else
{
if (tmpLength >= minx) continue;
//路程小于最小值,查询下个子节点
tmpPath += "," + node.CurrentNode.Name;
tmpPath = FindMinx(node.CurrentNode, dest, tmpLength, srcRank, tmpPath, ref minx);
if (tmpPath != "")
goalPath = tmpPath;
}
}
return goalPath;
} /// <summary>初始化图</summary>
/// <param name="list">图点集合</param>
private ConcurrentDictionary<String, Node> InitNode(IEnumerable<Map> list)
{
var node = new ConcurrentDictionary<String, Node>(); foreach (var item in list)
{
Node n1;
Node n2;
if (!node.ContainsKey(item.N1))
{
n1 = new Node(item.N1);
node.TryAdd(item.N1, n1);
}
else
{
n1 = node[item.N1];
}
if (!node.ContainsKey(item.N2))
{
n2 = new Node(item.N2);
node.TryAdd(item.N2, n2);
}
else
{
n2 = node[item.N2];
}
n1.LE.Add(new Edge(item.N2, item.Weight, n2));
}
return node;
} #region 拷贝
public object Clone()
{
return MemberwiseClone();
} /// <summary>浅拷贝</summary>
public Dijkstra CloneEntity()
{
return Clone() as Dijkstra;
}
#endregion
} /// <summary>
/// 节点
/// </summary>
public class Node : ICloneable
{
/// <summary>节点名称</summary>
public String Name { get; set; } /// <summary>节点边集合</summary>
public List<Edge> LE { get; set; } /// <summary>节点级别</summary>
public Int32 Rank { get; set; } /// <summary>最短距离</summary>
public Int32 MinDistance { get; set; } /// <summary>路径</summary>
public String Path { get; set; } /// <summary>查询标识</summary>
public bool IsFind { get; set; } public Node(String name)
{
Name = name;
IsFind = false;
Rank = -1;
MinDistance = 0;
LE = new List<Edge>();
} /// <summary>设置节点级别</summary>
/// <param name="parentNode">父节点</param>
public void SetRank(Node parentNode)
{
if (Rank != -1) return; Rank = parentNode != null ? parentNode.Rank + 1 : 0;
} /// <summary>获取节点级别</summary>
public Int32 GetRank()
{
return Rank;
} #region 拷贝
public object Clone()
{
return MemberwiseClone();
} /// <summary>浅拷贝</summary>
public Node CloneEntity()
{
return Clone() as Node;
}
#endregion
} /// <summary>
/// 节点边
/// </summary>
public class Edge : ICloneable
{
/// <summary>边名称</summary>
public String Name { get; set; } /// <summary>权值,代价 ,距离</summary>
public Int32 Weight { get; set; } /// <summary>当前向量终点节点</summary>
public Node CurrentNode { get; set; } public Edge(String name, Int32 weight, Node node)
{
Name = name;
Weight = weight;
CurrentNode = node;
} /// <summary>设置当前节点</summary>
/// <param name="node">当前向量终点节点</param>
public void SetCurrentNode(Node node)
{
CurrentNode = node;
} #region 拷贝
public object Clone()
{
return MemberwiseClone();
} /// <summary>浅拷贝</summary>
public Edge CloneEntity()
{
return Clone() as Edge;
}
#endregion } /// <summary>图型</summary>
public class Map : ICloneable
{
/// <summary>节点1</summary>
public string N1 { get; set; } /// <summary>节点2</summary>
public string N2 { get; set; } /// <summary>权值,代价 ,距离</summary>
public int Weight { get; set; } public Map()
{
} public Map(string n1, string n2, int weight)
{
N1 = n1;
N2 = n2;
Weight = weight;
} #region 拷贝
public object Clone()
{
return MemberwiseClone();
} /// <summary>浅拷贝</summary>
public Map CloneEntity()
{
return Clone() as Map;
}
#endregion } }

用法:

private IEnumerable<Map> InitMap()
{
var list = new List<Map>
{
new Map("A", "B", 3),
new Map("A", "C", 5),
new Map("A", "D", 2),
new Map("B", "A", 3),
new Map("B", "C", 4),
new Map("B", "E", 10),
new Map("C", "A", 5),
new Map("C", "B", 4),
new Map("C", "D", 2),
new Map("C", "F", 1),
new Map("C", "G", 6),
new Map("D", "A", 2),
new Map("D", "C", 2),
new Map("D", "H", 3),
new Map("E", "B", 10),
new Map("E", "F", 4),
new Map("E", "I", 2),
new Map("F", "C", 1),
new Map("F", "E", 4),
new Map("F", "K", 8),
new Map("F", "L", 2),
new Map("G", "C", 6),
new Map("G", "H", 8),
new Map("G", "L", 2),
new Map("H", "D", 3),
new Map("H", "G", 8),
new Map("I", "E", 2),
new Map("I", "K", 6),
new Map("I", "J", 1),
new Map("J", "I", 1),
new Map("J", "K", 9),
new Map("K", "J", 9),
new Map("K", "I", 6),
new Map("K", "F", 8),
new Map("K", "L", 5),
new Map("L", "K", 5),
new Map("L", "F", 2),
new Map("L", "G", 2)
};
return list;
} void 调用(){ var dij = new Dijkstra(InitMap(), start, end);
dij.Find();
var _path = string.Format("最短距离:{0} 路径:{1}{2} 总耗时:{3} 毫秒 \r\n", dij.EndNode.MinDistance, start, dij.EndNode.Path, sw.ElapsedMilliseconds); //在界面显示结果 }

友情连接

C# 迪杰斯特拉算法 Dijkstra的更多相关文章

  1. 迪杰斯特拉算法&lpar;Dijkstra&rpar; (基础dij&plus;堆优化) BY:优少

    首先来一段百度百科压压惊... 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最 ...

  2. 图-&gt&semi;最短路径-&gt&semi;单源最短路径&lpar;迪杰斯特拉算法Dijkstra&rpar;

    文字描述 引言:如下图一个交通系统,从A城到B城,有些旅客可能关心途中中转次数最少的路线,有些旅客更关心的是节省交通费用,而对于司机,里程和速度则是更感兴趣的信息.上面这些问题,都可以转化为求图中,两 ...

  3. 迪杰斯特拉算法dijkstra(可打印最短路径)

    #include <iostream> #include <iomanip> #include <string> using namespace std; #def ...

  4. 迪杰斯特拉(dijkstra)算法的简要理解和c语言实现(源码)

    迪杰斯特拉(dijkstra)算法:求最短路径的算法,数据结构课程中学习的内容. 1 . 理解 算法思想::设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合 ...

  5. 最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法.本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的 ...

  6. dijkstra算法(迪杰斯特拉算法)

    dijkstra算法(迪杰斯特拉算法) 用途:有向图最短路径问题 定义:迪杰斯特拉算法是典型的算法,一般的表述通常有两种方式,这里均采用永久和临时标号的方式,该算法要求图中不存在负权边 用永久和临时标 ...

  7. 理解最短路径——迪杰斯特拉(dijkstra)算法

    原址地址:http://ibupu.link/?id=29 1.       迪杰斯特拉算法简介 迪杰斯特拉(dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科 ...

  8. Dijkstra【迪杰斯特拉算法】

    有关最短路径的最后一个算法——Dijkstra 迪杰斯特拉算法是由荷兰计算机科学家迪杰斯特拉于1959 年提出的,因此又叫迪杰斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路 ...

  9. c&sol;c&plus;&plus; 图的最短路径 Dijkstra&lpar;迪杰斯特拉&rpar;算法

    c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法 图的最短路径的概念: 一位旅客要从城市A到城市B,他希望选择一条途中中转次数最少的路线.假设途中每一站都需要换车,则这个问题反映到图上就是 ...

随机推荐

  1. Atitit 解决Unhandled event loop exception错误的办法

    Atitit 解决Unhandled event loop exception错误的办法 查看workspace/.metadata/.log org.eclipse.swt.SWTError: No ...

  2. &lbrack;Deprecated&excl;&rsqb; Android开发案例 - 微博正文

    Deprecated! 更好的实现方式: 使用 android.support.design.widget.CoordinatorLayout. 本文详细介绍如何实现如下图中的微博正文页面效果, 其中 ...

  3. Codeforces Round &num;191 &lpar;Div&period; 2&rpar; E题

    状态压缩DP,算sum,本来是枚举的,结果TLE了.. #include <iostream> #include <cstring> #include <cstdio&g ...

  4. Scut 进阶:网络模型拓扑

    处理消息流程: 关于是否能用 json 串作为 response? 在最后写消息的时候要加上控制选项,将Response类型,事直接以字节流,还是转json串再转字节流的方式进行编码了,如果要转jso ...

  5. oracle12c:通过oracle客户端工具配置tns,并使用sqlldr进行批量导入数据

    通过oracle客户端工具配置tns: 进入oracle配置工具“Net Configuration Assistant”-> 点击“下一步”,完成tns配置. 测试是否tns可用 命令:tns ...

  6. vue&plus;axios 前端实现的常用拦截

    一.路由拦截使用 首先在定义路由的时候就需要多添加一个自定义字段requireAuth,用于判断该路由的访问是否需要登录.如果用户已经登录,则顺利进入路由,否则就进入登录页面,路由配置如下: cons ...

  7. Python循环&lowbar;for&amp&semi;while

    格式:for x in xs['James','Lily','Candy']: print(x) —————————————————————————————————— for循环就是把每个元素代入变量 ...

  8. Windows Server2008、IIS7启用CA认证及证书制作完整过程

    1         添加活动目录证书服务 1.1          打开服务器管理器,右键点击角色,选择“添加角色”,在“添加角色向导”窗口左侧面板选择“服务器角色”,然后勾选“Active Dire ...

  9. requests库入门07-patch请求

    使用data参数提交 设置邮件能见度,这个接口用来设置邮件是公共可见,还是私有的 import requests test_url = 'https://api.github.com' def get ...

  10. JavaFx 中常见的包和类(javafx笔记 )

    JavaFx 中常见的包和类(javafx笔记 ) 更多详细内容请参考<Pro JavaFX 8>. javafx.stage 包包含以下类: Stage 类 ​ Stage 类是任何 J ...