C#，图论与图算法，图最短路径的迪杰斯特拉（Dijkstra）算法与源代码

给定一个图和图中的源顶点，查找从源到给定图中所有顶点的最短路径。

Dijkstra的算法与Prim的最小生成树算法非常相似。像Prim的MST一样，我们生成一个以给定源为根的SPT（最短路径树）。我们维护两个集合，一个集合包含最短路径树中包含的顶点，另一个集合包含最短路径树中尚未包含的顶点。在算法的每个步骤中，我们都会找到另一个集合（尚未包含的集合）中的顶点，该顶点与源之间的距离最小。

下面是Dijkstra算法中使用的详细步骤，用于查找从单个源顶点到给定图中所有其他顶点的最短路径。

算法

1） 创建一个集sptSet（最短路径树集），用于跟踪最短路径树中包含的顶点，即计算并最终确定其与源的最小距离。最初，此集合为空。

2） 为输入图形中的所有顶点指定距离值。将所有距离值初始化为无穷大。将源顶点的距离值指定为0，以便首先拾取该顶点。

3） 而sptSet不包括所有顶点

….a） 拾取sptSet中不存在且具有最小距离值的顶点u。

….b） 包括u到sptSet。

….c） 更新u的所有相邻顶点的距离值。若要更新距离值，请遍历所有相邻顶点。对于每个相邻顶点v，如果u（从源）的距离值和边u-v的权重之和小于v的距离值，则更新v的距离值。

Dijkstra算法允许我们找到图中任意两个顶点之间的最短路径。

它不同于最小生成树，因为两个顶点之间的最短距离可能不包括图的所有顶点。

Djikstra在相反的方向上使用了这个属性，即我们高估了每个顶点到起始顶点的距离。然后我们访问每个节点及其邻居，以找到这些邻居的最短子路径。

该算法使用贪婪的方法，即我们找到下一个最佳解决方案，希望最终结果是整个问题的最佳解决方案。

参考：

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711?spm=1001.2014.3001.5501

Djikstra算法源程序：

using System;
using System.Text;

namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		private static int Minium_Distance(int Vertex_Number, int[] dist, bool[] sptSet)
		{
			int min = int.MaxValue;
			int min_index = -1;
			for (int v = 0; v < Vertex_Number; v++)
			{
				if (sptSet[v] == false && dist[v] <= min)
				{
					min = dist[v];
					min_index = v;
				}
			}
			return min_index;
		}

		public static int[] Dijkstra(int Vertex_Number, int[,] graph, int src)
		{
			int[] dist = new int[Vertex_Number];

			bool[] sptSet = new bool[Vertex_Number];

			for (int i = 0; i < Vertex_Number; i++)
			{
				dist[i] = int.MaxValue;
				sptSet[i] = false;
			}
			dist[src] = 0;

			for (int count = 0; count < Vertex_Number - 1; count++)
			{
				int u = Minium_Distance(Vertex_Number, dist, sptSet);

				sptSet[u] = true;

				for (int v = 0; v < Vertex_Number; v++)
				{
					if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
					{
						dist[v] = dist[u] + graph[u, v];
					}
				}
			}
			return dist;
		}
	}

	public static partial class GraphDrives
	{
		public static string Dijkstra()
		{
			int[,] graph = new int[,] {
				{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
				{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
				{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
				{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
				{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
				{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
				{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
				{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
				{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
			};

			StringBuilder sb = new StringBuilder();
			sb.AppendLine("Vertex	 Distance from Source<br>");
			sb.AppendLine("<style>");
			sb.AppendLine("td { padding:5px;text-align:right; }");
			sb.AppendLine("</style>");
			sb.AppendLine("<table width='100%' border=1 bordercolor='#999999' style='border-collapse:collapse;'>");
			sb.AppendLine("<tr>");
			sb.AppendLine("<td></td>");
			for (int j = 0; j < 9; j++)
			{
				sb.AppendLine("<td style='background-color:#EEEEFF;'>" + j + "</td>");
			}
			sb.AppendLine("</tr>");
			for (int i = 0; i < 9; i++)
			{
				int[] dist = Graph.Dijkstra(9, graph, i);
				sb.AppendLine("<tr>");
				sb.AppendLine("<td style='background-color:#EEEEFF;'>" + i + "</td>");
				for (int j = 0; j < 9; j++)
				{
					sb.AppendLine("<td>" + dist[j] + "</td>");
				}
				sb.AppendLine("</tr>");
			}
			sb.AppendLine("</table>");
			return sb.ToString();
		}
	}
}

POWER BY 315SOFT.COM