Dijstra算法代码,C代码库,德仔网

代码语言

代码分类

【C】 Dijstra算法

作者:DDT / 发布于2012/7/23/ 490

<div>using System;
using System.Collections;
using System.Text;

namespace Greedy
{  
class Marx
{
private int[] distance;       
private int row;
private ArrayList ways = new ArrayList();

public Marx(int n,params int[] d)
{
this.row = n;
distance = new int[row * row];
for (int i = 0; i < row * row; i++)
{
this.distance[i] = d[i];             
}
for (int i = 0; i < this.row; i++)  //有row个点，则从中心到各点的路有row-1条
{
ArrayList w = new ArrayList();
int j = 0;
w.Add(j);
ways.Add(w);
}
}
//------------------------------
public void Find_way()
{
ArrayList S = new ArrayList(1);
ArrayList Sr = new ArrayList(1);
int []Indexof_distance=new int[this.row];

for(int i=0; i < row; i++)
{
Indexof_distance[i]=i;
}

S.Add( Indexof_distance[0] );       

for (int i = 0; i < this.row; i++)
{
Sr.Add( Indexof_distance[i] );
}
Sr.RemoveAt(0);
int[] D = new int[this.row];    //存放中心点到每个点的距离

//---------------以上已经初始化了，S和Sr(里边放的都是点的编号)------------------
int Count = this.row - 1;
while (Count>0)
{
//假定中心点的编号是0的贪吃法求路径
for (int i = 0; i < row; i++)
D[i] = this.distance[i];

int min_num = (int)Sr[0];  //距中心点的最小距离点编号

foreach (int s in Sr)
{
if (D[s] < D[min_num]) min_num = s;
}

//以上可以排序优化
S.Add(min_num);
Sr.Remove(min_num);
//-----------把最新包含进来的点也加到路径中-------------
((ArrayList)ways[min_num]).Add(min_num);
//-----------------------------------------------
foreach (int element in Sr)
{
int position = element * (this.row) + min_num;
bool exchange = false;      //有交换标志

if (D[element] < D[min_num] + this.distance[position])
D[element] = D[element];
else
{
D[element] = this.distance[position] + D[min_num];
exchange = true;
}
//修改距离矩阵                  
this.distance[element] = D[element];
position = element * this.row;     
this.distance[position] = D[element];

//修改路径---------------
if (exchange == true)
{                      
((ArrayList)ways[element]).Clear();
foreach (int point in (ArrayList)ways[min_num])
((ArrayList)ways[element]).Add(point);
}
}
--Count;
}
}
//----------------------------------------------------
public void Display()
{        
//------中心到各点的最短路径----------
Console.WriteLine("中心到各点的最短路径如下: \n\n");
int sum_d_index = 0;
foreach(ArrayList mother in ways)
{
foreach (int child in mother)
Console.Write("V{0} -- ", child+1);
Console.WriteLine("    路径长 {0}",distance[sum_d_index++]);
}
}
}

class MainEnterPoint
{  
static void Main(string[] args)
{
int r;     //列数
Console.Write("请输入点个数（含配送中心点）: ");
Int32.TryParse(Console.ReadLine(), out r);
Console.WriteLine("各点分别为: \n");
for (int i = 0; i < r; i++)
Console.Write("V{0} ", i);
Console.Write("  假定第一个点是配送中心");
Console.WriteLine("\n\n输入各点之间的距离(无通径的用个大整数表示)\n");

int[] a = new int[r * r];           
int da;

for (int i = 0; i < r; i++)
{
for (int j = i + 1; j < r; j++)
{
Console.Write("V{0} 到 V{1}的距离是:  ",i,j);
Int32.TryParse(Console.ReadLine(), out da);
a[i * r + j] = da;
Console.WriteLine();
}
}
//----完善距离矩阵(距离矩阵其实可以是个上三角矩阵，
//----但为了处理方便，还是将其完整成一个对称阵)-----------
for (int i = 0; i < r; i++)
{
for (int j = 0; j < r; j++)
{
if (i == j)
{
a[i * r + j] = 0;
}
a[j * r + i] = a[i * r + j];
}
}     
Marx m=new Marx(r,a);
Console.WriteLine();
m.Find_way();
m.Display();
}
}
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　Dijstra　

同语言下

可能有用的

DDT贡献的其它代码(160)