程序测试代码如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace TestGraph
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("图(Graph)是由顶点(Vertex)和边(Edge)组成,下面程序演示最短路径...");
Graph graph = new Graph();
graph.Init();
graph.Path();
graph.Print();
Console.ReadLine();
}
}
class Graph
{
/// <summary>
/// 顶点个数
/// </summary>
public const int VertexCount = 6;
/// <summary>
/// 无法直接到达的距离，无限远的距离
/// </summary>
public const int Infinity = 99999;
/// <summary>
/// 顶点组成的数组
/// </summary>
public Vertex[] VertexArr = new Vertex[VertexCount];
/// <summary>
/// 起始顶点到每个顶点之间的最短距离组成的数组
/// </summary>
public MinDistance[] MinDistanceArr = new MinDistance[VertexCount];
/// <summary>
/// 顶点到顶点之间组成的矩阵数组
/// </summary>
public int[,] Matrix = new int[VertexCount, VertexCount];
/// <summary>
/// 当前索引
/// </summary>
public int CurrentIndex = 0;
/// <summary>
/// 添加一个顶点
/// </summary>
/// <param name="label"></param>
public void AddVertex(string label)
{
if (CurrentIndex >= VertexCount)
{
throw new Exception("添加顶点已超过限度个数：" + VertexCount);
}
VertexArr[CurrentIndex] = new Vertex(label);
CurrentIndex++;
}
/// <summary>
/// 添加一条边【认为距离是无向的 即A→B，同时B→A】
/// </summary>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
/// <param name="distance"></param>
public void AddEdge(int startIndex, int endIndex, int distance)
{
Matrix[startIndex, endIndex] = distance;
//如果距离是有方向的，则去掉下面一行
Matrix[endIndex, startIndex] = distance;
}
/// <summary>
/// 初始化
/// </summary>
public void Init()
{
AddVertex("A");//0
AddVertex("B");//1
AddVertex("C");//2
AddVertex("D");//3
AddVertex("E");//4
AddVertex("F");//5
//初始化最短距离为无穷大，所有矩阵距离都为无穷大
for (int i = 0; i < VertexCount; i++)
{
MinDistanceArr[i] = new MinDistance { ParentIndex = 0, Distance = Infinity };
for (int j = 0; j < VertexCount; j++)
{
Matrix[i, j] = Infinity;
}
}
//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);
}
/// <summary>
/// 找出最短路径
/// </summary>
public void Path()
{
//假设定义起点为A
int startIndex = 0;
VertexArr[startIndex].IsVisited = true;
for (int i = 0; i < VertexCount; i++)
{
if (Matrix[startIndex, i] < MinDistanceArr[i].Distance)
{
MinDistanceArr[i].Distance = Matrix[startIndex, i];
}
}
for (int cnt = 1; cnt < VertexCount; cnt++)
{
//找出未访问的顶点中，距离最小的顶点的起点索引
int minIndex = -1;//最小距离所在的索引
int minDist = Infinity;//最小距离
for (int i = 0; i < VertexCount; i++)
{
if (!VertexArr[i].IsVisited && MinDistanceArr[i].Distance < minDist)
{
minIndex = i;
minDist = MinDistanceArr[i].Distance;
}
}
//则最短路径被范围，并且找出更短的距离
VertexArr[minIndex].IsVisited = true;
for (int i = 0; i < VertexCount; i++)
{
//如果当前节点未访问，并且 最短距离+【最短距离的顶点可到达的顶点的距离之和】
if (!VertexArr[i].IsVisited && minDist + Matrix[minIndex, i] < MinDistanceArr[i].Distance)
{
MinDistanceArr[i].Distance = minDist + Matrix[minIndex, i];
MinDistanceArr[i].ParentIndex = minIndex;
}
}
}
}
/// <summary>
/// 打印消息
/// </summary>
public void Print()
{
for (int i = 0; i < VertexCount; i++)
{
Console.WriteLine("最短路径长度：A->{0}:{1},上一父节点:{2}.完全路线：{3}",
VertexArr[i].Label, MinDistanceArr[i].Distance, MinDistanceArr[i].ParentIndex, GetSerialPath(i));
}
}
/// <summary>
/// 获取连续节点路线
/// </summary>
/// <param name="parentIndex"></param>
/// <returns></returns>
public string GetSerialPath(int parentIndex)
{
Stack<string> stack = new Stack<string>();
stack.Push(VertexArr[parentIndex].Label);
while (parentIndex != 0)
{
parentIndex = MinDistanceArr[parentIndex].ParentIndex;
stack.Push(VertexArr[parentIndex].Label);
}
return string.Join("->", stack);
}
}
/// <summary>
/// 顶点
/// </summary>
class Vertex
{
/// <summary>
/// 是否已访问该顶点
/// </summary>
public bool IsVisited { get; set; }
/// <summary>
/// 顶点名称
/// </summary>
public string Label { get; set; }
public Vertex(string label)
{
this.IsVisited = false;
this.Label = label;
}
}
/// <summary>
/// 最短距离：两个顶点之间的最短距离
/// </summary>
class MinDistance
{
/// <summary>
/// 上一节点索引
/// </summary>
public int ParentIndex { get; set; }
/// <summary>
/// 最短距离
/// </summary>
public int Distance { get; set; }
}
}
程序运行效果如图：
因为之前刚写过
最小
生成树
算法
，刚开始看到Dijkstra
算法
的时候，因为要求各点到源点的最短距离，会想着直接从
最小
生成树的也是每找到最短的距离点加进来，但是后面仔细想了下，又翻了下定义，得到
最短路径
是一个
图
中2个点的最短距离。
最小
生成树是连接所有的点的路径最短，但是不一定是任意两点的距离
最小
，例如：
QuickGraph: A 100%
C#
graph library with Graphviz Support.---不错，不是很懂，因为我的数学不好！
http://www.codeproject.com/cs/miscctrl/quickgraph.asp
简介
图
表示点之间的关系，在
C#
中通过节点对象的集合来表示点(Vertex)，用邻接矩阵(adjacency matrix)来表示点之间的关系。下面来看
C#
实现。 PS:本片文章是我复习的笔记，代码注释很全。勿吐槽。 表示点的对象 下面实现代码: class Vertex
public string Data;
...
C#
窗体应用中使用ZedGraph曲线插件绘制
图
表：
https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/99716066
Winforn中设置ZedGraph曲线
图
的属性、坐标轴属性、刻度属性：
https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details...
Description
平面上有n个点(N<=100)，每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点直线的距离。现在的任务是找出从一点到另一点之间的
最短路径
。
Input
输入文件short.in，共有n+m+3行，其中：
第一行为一个整数n。
第2行到第n+1行（共n行），每行的两个整数x和y，描述一个点的坐标(以一个空格隔开)。
第n+2行为一个整数m，表示
图
中的连线个数。
此后的m行，每行描述一条连
构造类并实现
最短路径
方法
在前面的
C#
编程中，我们已经完成了诸如遍历、
最小
生成树等许多方法，这个类已经可以完成诸如邻接矩阵输入、顶点矩阵输入问题。这个类在Graph2.cs中。
现在，我们新建立一个WINDOWS工程，位置在
C#
\Dijstra文件夹下，并把Graph.cs复制到该文件夹下，并让你的工程引用它。
Graph.cs及
最短路径
Dijstra方法如下：
using System;
using System.Collection
