dijkstra赋权有向图最短路径算法c#初步实现
da,da,da,da来点节奏(广场舞走起,刚刚母亲去跳广场舞了),请记住这个名字,这个伟大人物的名字。
下面是c#代码初步实现,总算完成了,完成了就是好的,以后继续改进:
namespace dijkstra改进
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
//图顶点v1,v2,v3,v4,v5,v6,v7,v8,v9
//图顶点对应的有向边及权值
Point[] edge = new Point[14];//edge[0].(1,2)指定第一条边方向是顶点1(x)到达顶点2(y)
int[] Wxy = new int[14];//Wxy[0]表示第一条边对应的权值,也就是w12的值对应edage[0].(1,2)
edge[0] = new Point(1, 2); Wxy[0] = 6;//wx=1,wy=2
edge[1] = new Point(1, 4); Wxy[1] = 1;//wx=1,wy=4
edge[2] = new Point(1, 3); Wxy[2] = 3;//wx=1,wy=3
edge[3] = new Point(3, 2); Wxy[3] = 2;//wx=3,wy=2
edge[4] = new Point(3, 4); Wxy[4] = 2;//wx=3,wy=4
edge[5] = new Point(2, 5); Wxy[5] = 1;
edge[6] = new Point(4, 6); Wxy[6] = 10;
edge[7] = new Point(5, 4); Wxy[7] = 6;
edge[8] = new Point(5, 6); Wxy[8] = 4;
edge[9] = new Point(5, 7); Wxy[9] = 3;
edge[10] = new Point(5, 8); Wxy[10] = 6;
edge[11] = new Point(6, 5); Wxy[11] = 10;
edge[12] = new Point(6, 7); Wxy[12] = 2;
edge[13] = new Point(7, 8); Wxy[13] = 4;
List<Point> Ps = new List<Point>();//用来存P标号
int[] Tv确定 = new int[9]; //用来计算T标号
int[] Plamuda = new int[9];
for (int i = 0; i < 9; i++)
{
Tv确定[i] = 65535;//初始化为最大值
Plamuda[i] = 9;//初始化为最大值
}
int 退出循环条件 = 7;
int tempV = 1;//顶点1,p值为0,=(1,0)=x,y
int tempP = 0;
Point pt = new Point(tempV, tempP);
Ps.Add(pt);
Plamuda[tempV - 1] = 0;//顶点tempv赋值不再等于9,更新了,与Ps搭配配对
do//经过测试Ps.count==7不再发生变化,退出,补充未录入那最后一个
{
if (Ps.Count >= 7) break;
for (int 元素 = 0; 元素 < 14; 元素++)//14条有向边
{
//if (edge[元素].X == 1)//找出顶点1打头的权值
if (edge[元素].X ==Ps[Ps.Count - 1].X)//找出顶点X打头的权值
{
int Tvnew = Ps[Ps.Count - 1].Y + Wxy[元素];
if (Tvnew < Tv确定[edge[元素].Y - 1])
{
//先把Tv确定几个值整到list中去
Tv确定[edge[元素].Y - 1] = Tvnew;
//Plamuda[edge[元素].Y - 1] = 1;//顶点1打头的有向边终点lamuda值
Plamuda[edge[元素].Y - 1] = Ps[Ps.Count - 1].X;//顶点X打头的有向边终点lamuda值
}
}
}
int index = minTv确定(Tv确定);//返回序号,知道是哪一个顶点
//然后找出Tv确定最小给Ps(最小由T转P)//第一次经过筛选是顶点4
tempV = index;//顶点4,p值为1,=(4,1)=x,y
tempP = Tv确定[index - 1];
for(int err=0;err<Ps.Count;err++)//进入P标号顶点重复处理
{
if (tempV == Ps[err].X)
{ //如果相同,干掉后来这个
Tv确定[tempV - 1] += 65535;
}
}
if (Tv确定[tempV - 1] >= 65535) continue;//进入P标号顶点重复处理
Ps.Add(new Point(tempV, tempP));//如果P标号顶点不重复
// Plamuda[tempV - 1] = 1;//顶点tempv赋值不再等于9,更新了,与Ps搭配配对
Tv确定[tempV - 1] += 65535;
//继续迭代while循环//顶点打头变为4
}
while (true) ;
// Tv确定中还有2个值,Tv确定[4]=12,Tv确定[8]=12,因为ps[4]=1,故Tv确定[4]作废,
//所以最后录入Tv确定[8]=12=ps[8]
Ps.Add(new Point(8, 12));//顶点8,值为12
//结束dijkstra.ok!!!!!!!!!!!!!!!!!!!!!!!!!!202009271629
}
int minTv确定(int[] arr)//返回序号,知道是哪一个
{
int temp = 65535; int index = -1;
for (int i = 0; i < arr.GetLength(0); i++)
{
if (arr[i] < temp)
{
temp = arr[i];
index = i;
}
}
return index + 1;
}
}
}
运行结果:
为什么lmuda【3】=5?应该是1啊!Tv确定是T标号。
说明,x=1,4,3,2,5,7,6,8意思是顶点1,4,3,2,5,7,6,8的P标号,他们对应的值是y=0,1,3,5,6,9,10,12=p(v1),p(v4),p(v3),p(v2),p(v5),p(v7),p(v6),p(v8);关键的P标号ok!lumda虽然没那么重要,回头再查查,找找问题。