# 广度优先算法代码示例

using System;
using System.Collections.Generic;
public class DijkstraAlgorithm
{
// Dijkstra算法主要逻辑
public static void Dijkstra(Dictionary<int, List<Edge>> graph, int startNode, int endNode)
{
// 存储节点到起点的距离
Dictionary<int, int> distances = new Dictionary<int, int>();
// 存储节点的父节点，用于构建最短路径
Dictionary<int, int> parents = new Dictionary<int, int>();
// 优先队列，用于按照节点距离从小到大的顺序处理
PriorityQueue priorityQueue = new PriorityQueue();
// 初始化distances和parents字典
foreach (int node in graph.Keys)
{
distances[node] = int.MaxValue; // 将所有节点的距离初始化为无穷大
parents[node] = -1; // 将所有节点的父节点初始化为-1
}
distances[startNode] = 0; // 将起始节点的距离设置为0
priorityQueue.Enqueue(new Node(startNode, 0)); // 将起始节点加入优先队列
// 开始执行Dijkstra算法
while (priorityQueue.Count > 0) // 当优先队列不为空时
{
Node currentNode = priorityQueue.Dequeue();

// 如果当前节点的距离值大于distances中对应节点的距离值，说明当前节点已经被处理过，直接跳过
if (currentNode.Value > distances[currentNode.Vertex])
continue;
// 对当前节点的所有相邻边进行遍历
foreach (Edge edge in graph[currentNode.Vertex])
{
// 计算从起始节点经过当前节点到目标节点的新距离
int newDistance = distances[currentNode.Vertex] + edge.Weight;
// 如果新距离小于distances中对应节点的距离值
if (newDistance < distances[edge.Destination])
{
distances[edge.Destination] = newDistance; // 更新目标节点的距离值
parents[edge.Destination] = currentNode.Vertex; // 更新目标节点的父节点
priorityQueue.Enqueue(new Node(edge.Destination, newDistance)); // 将目标节点加入优先队列
}
}
}
// 判断是否存在从起点到终点的路径
if (distances[endNode] == int.MaxValue)
{
Console.WriteLine("There is no path from startNode to endNode.");
}
else
{
// 获取最短路径
List<int> shortestPath = GetShortestPath(parents, startNode, endNode);
Console.WriteLine(\$"Shortest distance from {startNode} to {endNode}: {distances[endNode]}");
Console.WriteLine("Shortest path: " + string.Join(" -> ", shortestPath));
}
}
// 构建最短路径
public static List<int> GetShortestPath(Dictionary<int, int> parents, int startNode, int endNode)
{
List<int> path = new List<int>();
int currentNode = endNode;
while (currentNode != -1)
{
path.Insert(0, currentNode); // 将节点插入到路径列表的开头
currentNode = parents[currentNode]; // 更新当前节点为父节点
}
return path;
}
public static void Main(string[] args)
{
Dictionary<int, List<Edge>> graph = new Dictionary<int, List<Edge>>();
// 创建图形
// 每个键表示一个节点，每个值表示与该节点相连的所有边
graph[0] = new List<Edge>
{
new Edge(1, 2),
new Edge(2, 5),
new Edge(3, 9)
};
graph[1] = new List<Edge>
{
new Edge(4, 12)
};
graph[2] = new List<Edge>
{
new Edge(4, 5),
new Edge(5, 6)
};
graph[3] = new List<Edge>
{
new Edge(5, 10)
};
graph[4] = new List<Edge>
{
new Edge(6, 6)
};
graph[5] = new List<Edge>
{
new Edge(6, 5),
new Edge(7, 4)
};
graph[6] = new List<Edge>
{
new Edge(8, 8)
};
graph[7] = new List<Edge>
{
new Edge(8, 5),
new Edge(9, 7)
};
graph[8] = new List<Edge>
{
new Edge(9, 8)
};
graph[9] = new List<Edge>();
int startNode = 0;
int endNode = 9;
// 执行Dijkstra算法
Dijkstra(graph, startNode, endNode);
}
}
// 边类，表示节点之间的连接关系
public class Edge
{
public int Destination { get; } // 目标节点
public int Weight { get; } // 边的权重
public Edge(int destination, int weight)
{
Destination = destination;
Weight = weight;
}
}
// 节点类，包含节点编号和距离值
public class Node
{
public int Vertex { get; } // 节点编号
public int Value { get; } // 节点距离值
public Node(int vertex, int value)
{
Vertex = vertex;
Value = value;
}
}
// 优先队列类，用于保存节点，并确保按照节点的距离值从小到大排序
public class PriorityQueue
{
private List<Node> heap; // 存放节点的列表
public int Count => heap.Count;
public PriorityQueue()
{
heap = new List<Node>();
}
// 入队操作，将节点加入优先队列并保持有序
public void Enqueue(Node item)
{
int currentIndex = heap.Count - 1;
while (currentIndex > 0)
{
int parentIndex = (currentIndex - 1) / 2;
if (heap[currentIndex].Value >= heap[parentIndex].Value)
break;
Swap(currentIndex, parentIndex);
currentIndex = parentIndex;
}
}
// 出队操作，取出距离值最小的节点
public Node Dequeue()
{
if (Count == 0)
throw new InvalidOperationException("PriorityQueue is empty.");
Node item = heap[0];
heap[0] = heap[Count - 1];
heap.RemoveAt(Count - 1);
int currentIndex = 0;
while (currentIndex < Count)
{
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
if (leftChildIndex >= Count)
break;
int smallerChildIndex = leftChildIndex;
if (rightChildIndex < Count && heap[rightChildIndex].Value < heap[leftChildIndex].Value)
smallerChildIndex = rightChildIndex;
if (heap[currentIndex].Value <= heap[smallerChildIndex].Value)
break;
Swap(currentIndex, smallerChildIndex);
currentIndex = smallerChildIndex;
}
return item;
}
// 交换两个位置的节点
private void Swap(int index1, int index2)
{
Node temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}

|
1天前
|

【8月更文挑战第6天】在机器学习领域，支持向量机（SVM）犹如璀璨明珠。它是一种强大的监督学习算法，在分类、回归及异常检测中表现出色。SVM通过在高维空间寻找最大间隔超平面来分隔不同类别的数据，提升模型泛化能力。为处理非线性问题，引入了核函数将数据映射到高维空间。SVM在文本分类、图像识别等多个领域有广泛应用，展现出高度灵活性和适应性。
12 2
|
21天前
|

Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
127 2
|
3天前
|

【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM（实为KMP，Knuth-Morris-Pratt）算法，虽主要用于字符串匹配，但其生成的前缀函数（next数组）也可用于求解最小周期。核心思想是构建LPS数组，记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S，其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性，可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期，体现了KPM算法在解决此类问题上的高效性。
12 0
|
29天前
|

Python算法高手的必修课：深入理解分治法、贪心算法、动态规划，让你的代码更智能！
【7月更文挑战第9天】在Python算法学习中，分治法（如归并排序）将大问题分解为小部分递归解决；贪心算法（如货币找零）在每步选择局部最优解尝试达到全局最优；动态规划（如斐波那契数列）通过存储子问题解避免重复计算，解决重叠子问题。掌握这三种方法能提升代码效率，解决复杂问题。
28 1
|
17天前
|

14 0
|
17天前
|

15 0
|
20天前
|

MCKP-MMF算法是一种启发式流量估计方法，用于寻找无线传感器网络的局部最优解。它从最小配置开始，逐步优化部分解，调整访问点的状态。算法处理访问点的动态影响半径，根据带宽需求调整，以避免拥塞。在MATLAB 2022a中进行了仿真，显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段：慢启动阶段识别瓶颈并重设半径，随后进入周期性调整阶段，追求最大最小公平性。
30 1
|
4天前
|

17 4
|
2天前
|

11 2
|
12天前
|

35 12