CSDN话题挑战赛第2期
参赛话题：算法题解
学习算法可能是为了面试也可能是为了竞赛，记录自己写下的题目，整理成一篇精美的题解，不仅能加深自己的印象，还能帮助学习算法的他人，更主要是为了检验自己是否掌握了这道题，一起来将你刷的题目整理成题解吧！
1.题目描述
已知A，B，C，D，E，F六个顶点，图是无向图，计算出起点A到其他顶点的最短距离以及路径
2.题目链接：之前我的一份博客最短路径算法
3.思路讲解
①InitGraph() 初始化图的顶点，边，以及最短距离默认为无穷大
②GetRouterPath() 设置第一个顶点A到其他顶点的距离是直连的
~如果当前顶点A到其他顶点的距离小于Infinity，就以当前距离作为初始最小的距离
~找出未访问的顶点中，距离最小的顶点的顶点，然后标记顶点为已访问的
~如果当前节点未访问，并且 最短距离+【最短距离的顶点可到达的顶点的距离之和】，那么就设置当前路径为最小距离 需要一个双重循环
4.模板代码
新建窗体应用程序GraphDemo，将默认的Form1修改为FormGraph
窗体设计如图：
新建关键路径类Graph.cs：
类Graph的源程序如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GraphDemo
{
/// <summary>
/// 图【Graph】是由顶点【Vertex】以及顶点之间的连线组成的边【Edge】组成，即(V,E)
/// 根据需求不同，图分为 有向图 和 无向图两种，本文只考虑无向图
/// 斯内科 20220926
/// </summary>
public class Graph
{
/// <summary>
/// 顶点个数
/// </summary>
public const int VertexCount = 6;
/// <summary>
/// 无法直接到达的距离，无限远的距离
/// </summary>
public const int Infinity = 99999;
/// <summary>
/// 图的顶点集合，数组的每一个元素代表一个顶点【元组的第一项代表顶点名称，第二项代表是否已被访问】
/// </summary>
public Tuple<string, bool>[] VertexTuples = new Tuple<string, bool>[VertexCount];
/// <summary>
/// 表示两点之间的距离。如：
/// MatrixDistance[0,1]=88 表示 【索引为0的顶点】 到 【索引为1的顶点】 之间的距离是88
/// </summary>
public int[,] MatrixDistance = new int[VertexCount, VertexCount];
/// <summary>
/// 起点到终点的最短距离
/// 元组的第一项代表起点名称，第二项代表终点名称，第三项代表最短距离值，第四项代表当前最短距离的上一个顶点索引
/// 本文起点名称固定设置为A，获取A到其他任何一个顶点之间的最短距离，以及运行轨迹路线
/// </summary>
public Tuple<string, string, int, int>[] MinDistanceTuples = new Tuple<string, string, int, int>[VertexCount];
/// <summary>
/// 初始化【权重图】或【距离图】：
/// 一、初始化所有顶点，并标记所有顶点都是未访问的
/// 二、初始化任意两点的距离都是无穷大的
/// 三、图的实际距离【两点之间可以直接连接的部分，也就是 直接连接的顶点之间的距离 覆盖原来的默认值无穷大】
/// </summary>
public void InitGraph()
{
InitVertex();
//初始化最短距离为无穷大，所有矩阵距离都为无穷大
for (int i = 0; i < VertexCount; i++)
{
for (int j = 0; j < VertexCount; j++)
{
MatrixDistance[i, j] = Infinity;
}
}
#region 添加边Edge：图的连线部分
//AB AC AD
AddEdge(0, 1, 5);
AddEdge(0, 2, 3);
AddEdge(0, 3, 19);
//BC BE
AddEdge(1, 2, 10);
AddEdge(1, 4, 8);
//CD CE CF
AddEdge(2, 3, 14);
AddEdge(2, 4, 12);
AddEdge(2, 5, 9);
//DE DF
AddEdge(3, 4, 5);
AddEdge(3, 5, 4);
//EF
AddEdge(4, 5, 4);
#endregion
#region 默认最短距离为无穷大
for (int i = 0; i < VertexCount; i++)
{
MinDistanceTuples[i] = Tuple.Create(VertexTuples[0].Item1, VertexTuples[i].Item1, Infinity, 0);
}
#endregion
}
/// <summary>
/// 设置第一个顶点A到其他顶点的距离是直连的
/// ①如果当前顶点A到其他顶点的距离小于Infinity，就以当前距离作为初始最小的距离
/// ②找出未访问的顶点中，距离最小的顶点的顶点，然后标记顶点为已访问的
/// ③如果当前节点未访问，并且 最短距离+【最短距离的顶点可到达的顶点的距离之和】，那么就设置当前路径为最小距离 需要一个双重循环
/// </summary>
public void GetRouterPath()
{
int startIndex = 0;
//将第一个顶点更新为已访问
VertexTuples[startIndex] = Tuple.Create(VertexTuples[startIndex].Item1, true);
for (int i = 0; i < VertexCount; i++)
{
if (MatrixDistance[startIndex, i] < MinDistanceTuples[i].Item3)
{
//因元组无法为第三项赋值，只能重建元组了
MinDistanceTuples[i] = Tuple.Create(MinDistanceTuples[i].Item1, MinDistanceTuples[i].Item2, MatrixDistance[startIndex, i], startIndex);
}
}
for (int cnt = 1; cnt < VertexCount; cnt++)
{
//找出最小的距离对应的顶点索引,并将当前顶点设置为已访问
int minIndex = FindMinDistanceIndex();
int minDist = MinDistanceTuples[minIndex].Item3;
//设置为已访问该顶点
VertexTuples[minIndex] = Tuple.Create(VertexTuples[minIndex].Item1, true);
for (int i = 0; i < VertexCount; i++)
{
//如果当前节点未访问，并且 最短距离+【最短距离的顶点可到达的顶点的距离之和】 还要比原来的还要短，就用新的最短距离赋值
if (!VertexTuples[i].Item2 && minDist + MatrixDistance[minIndex, i] < MinDistanceTuples[i].Item3)
{
//记录上一个最短距离顶点的索引
MinDistanceTuples[i] = Tuple.Create(MinDistanceTuples[i].Item1, MinDistanceTuples[i].Item2, minDist + MatrixDistance[minIndex, i], minIndex);
}
}
}
}
/// <summary>
/// 显示最短路径的详细信息
/// </summary>
/// <param name="vertexIndex"></param>
/// <returns></returns>
public string DisplayDescription(int vertexIndex)
{
return $"最短路径长度：{VertexTuples[0].Item1}->{VertexTuples[vertexIndex].Item1}，最短距离{MinDistanceTuples[vertexIndex].Item3},上一个顶点索引:{MinDistanceTuples[vertexIndex].Item4}.\n" +
$" 完整路由：{GetSerialPath(vertexIndex)}";
}
/// <summary>
/// 获取连续节点路线
/// </summary>
/// <param name="parentIndex"></param>
/// <returns></returns>
private string GetSerialPath(int parentIndex)
{
Stack<string> stack = new Stack<string>();
stack.Push(VertexTuples[parentIndex].Item1);
while (parentIndex != 0)
{
parentIndex = MinDistanceTuples[parentIndex].Item4;
stack.Push(VertexTuples[parentIndex].Item1);
}
return string.Join("->", stack);
}
/// <summary>
/// 找出最小的距离对应的顶点索引
/// </summary>
/// <returns></returns>
private int FindMinDistanceIndex()
{
//找出未访问的顶点中，距离最小的顶点的起点索引
int minIndex = -1;//最小距离所在的索引
int minDist = Infinity;//最小距离
for (int i = 0; i < VertexCount; i++)
{
if (!VertexTuples[i].Item2 && MinDistanceTuples[i].Item3 < minDist)
{
minIndex = i;
minDist = MinDistanceTuples[i].Item3;
}
}
return minIndex;
}
/// <summary>
/// 初始化所有顶点
/// </summary>
private void InitVertex()
{
char label = 'A';
for (int i = 0; i < VertexTuples.Length; i++)
{
VertexTuples[i] = Tuple.Create(((char)(label + i)).ToString(), false);
}
}
/// <summary>
/// 添加一条无向边【认为距离是无向的 即A→B，同时B→A】
/// </summary>
/// <param name="startIndex">起始索引</param>
/// <param name="endIndex">到达索引</param>
/// <param name="distance">两点之间的距离</param>
private void AddEdge(int startIndex, int endIndex, int distance)
{
MatrixDistance[startIndex, endIndex] = distance;
//如果距离是有方向的，则去掉下面一行代码
MatrixDistance[endIndex, startIndex] = distance;
}
}
}
窗体FormGraph的主要源代码如下：
(忽略设计器自动生成的代码)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace GraphDemo
{
public partial class FormGraph : Form
{
public FormGraph()
{
InitializeComponent();
Image image = Image.FromFile(AppDomain.CurrentDomain.BaseDirectory + "graphDemo.png");
pictureBox1.Width = image.Width;
pictureBox1.Height = image.Height;
pictureBox1.Image = image;
}
private void btnGetPath_Click(object sender, EventArgs e)
{
rtxtMessage.Clear();
Graph graph = new Graph();
graph.InitGraph();
graph.GetRouterPath();
for (int i = 0; i < Graph.VertexCount; i++)
{
string pathDescription = graph.DisplayDescription(i);
DisplayMessage(pathDescription);
}
}
/// <summary>
/// 显示文本内容
/// </summary>
/// <param name="message"></param>
private void DisplayMessage(string message)
{
this.BeginInvoke(new Action(() =>
{
rtxtMessage.AppendText($"{DateTime.Now.ToString("HH:mm:ss.fff")}=>【{message}】\n");
}));
}
}
}
5.算法与时间复杂度
该算法时间复杂度为N*N
程序运行如图：
本文含有隐藏内容，请 开通VIP 后查看