dijkstra.txt

最短路的Dijkstra算法

using System; 
using System.Collections; 
using System.Collections.Generic; 


class Djst 
{       public  int N; 
public int[,] Data; 
public String[] NdName; 
public int[] Distan; 
       public  ArrayList P ,T; 
    
    
       public  Djst(int n, int[,]data, String []name) 
       { N=n; 
Data=new int[N,N]; 
NdName=new string[N]; 
Distan=new int[N]; 
  for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++) 
        Data[i,j]=data[i,j]; 
       for(int i=0;i<N;i++) 
        NdName[i]=name[i]; 
       Distan=new int[N]; 
       P = new ArrayList(); 
       T = new ArrayList(); 
       for(int i=0;i<N;i++) 
          T.Add(i); 
       } 
        

 public void Calc( ref int shortest, ref int[,] Pno) 
{ 
shortest=0; 
Pno=new int[N,N]; 
P.Add(0); 
T.Remove(0); 
Distan[0]=0; 
foreach (int  t in T) 
{   Distan[t]=Int16.MaxValue;} 

       L2: 
foreach(int  t in T) 
{       int d=Int16.MaxValue ; 
foreach (int p in P) 
{  int temp=Math.Min(Distan[t],Distan[p]+Data[p,t]); 
  if( temp<d ) d=temp; 
} 
               Distan[t]=d; 
        } 
int dd=Int16.MaxValue; 
int no=0; 
foreach (int t in T) 
{  if(Distan[t]<dd) {dd=Distan[t]; no=t;} 
} 
foreach(int p in P) 
{ if  ( Distan[p]+Data[p,no]==dd) 
      Pno[no,p]=1;  //p[后继,先驱];p是no的先驱 
} 
                 P.Add(no); 
T.Remove(no); 
if( no != N-1 ) goto L2; 
shortest=dd; 
} 
  
  
         public ArrayList list=new ArrayList(); 

public  void Display(int [,] pno,  int n)//这个Display递归函数显示所有的最短路径 
{     if(n==N-1) 
{       Console.Write("{0}  ",NdName[0]); 
foreach (int t in list)  {Console.Write("{0}  ",NdName[t]);} 
Console.Write("■\n"); 
return; 
} 
for(int i=0; i<N;i++) 
{ 
if  (pno[i,n]==1) 
{ 
                  list.Add(i); 
 Display(pno,i); 
 list.Remove(i); 
} 
} 

} 

    /********到此核心算法已完成, 以下是输入输出处理********/ 

public static void   Input(int r, ref string[] name,ref int[,]data) 
{     int X=Int16.MaxValue; 

int []dt=new int[r*(r-1)/2]; 
data=new int[r,r]; 
name=new string[r]; 

string  s; 
  
Console.WriteLine("输入{0}个结点的名称:",r); 
s=Console.ReadLine(); 
int i=0,j=0; 
name=s.Split(",".ToCharArray()); 

Console.WriteLine("输入(带权)邻接矩阵主对角线以上的元素(共{0}个):",r*(r-1)/2); 
i=0; 


 s=Console.ReadLine(); 
 string[] ss=new string [r*(r-1)/2]; 
  

ss=s.Split(",".ToCharArray() ); 

while(  i<r*(r-1)/2 ) 
{ 
if(ss[i].Contains("X") | ss[i].Contains("x") ) dt[i]=X; 
else dt[i]=Int32.Parse(ss[i]); 
i++; 
} 

for(i=0;i<r;i++) 
for(j=i+1;j<r;j++) 
data[i,j]=dt[(2*r-i-1)*i/2+j-i-1]; 

for(i=0;i<r;i++) 
for(j=0;j<i;j++) 
data[i,j]=data[j,i]; 
for(i=0;i<r;i++) 
data[i,i]=0; 


} 



 public static void Main() 
 { 
       int r,shortest=0; 
       Console.Clear(); 
       Console.SetWindowSize(80,25); 
        
       Console.ForegroundColor=ConsoleColor.Yellow; 
       Console.WriteLine("Dijkstra 算法  V0.9     CopyRight Gaspher"); 
       Console.WriteLine("输入结点的个数:"); 
                r=Int32.Parse(Console.ReadLine()); 
                string[] name=new string[r]; 
                int [,]data=new int[r,r]; 
                int [,]pno=new int [r,r]; 
       Input( r, ref name,ref data); 
      
  
 Console.WriteLine("你输入的矩阵是:\n"); 
for(int i=0;i<r;i++) 
{ for(int j=0;j<r;j++) 
{if(data[i,j]==Int16.MaxValue) Console.Write("X  "); 
        else Console.Write("{0}  ",data[i,j]); 
        if(j==r-1) Console.Write("\n");} 
} 

  Djst djst=new Djst(r,data,name); 
  djst.Calc(ref shortest, ref pno); 
  
 Console.WriteLine("\n最短路长为{0}.",shortest); 
 Console.WriteLine("所有最短路径如下:"); 
 djst.Display(pno,0); 

 Console.Write("回车键确认退出..."); 
 Console.ReadLine(); 
 } 
}