dijkstra.txt

Dijkstra算法是典型最短路算法

void Dijkstra(int n,int[] Distance,int[] iPath)
{
int MinDis,u;
int i,j;
//从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[]
for(i=0;i<VerNum;i++)
{
   Distance[i]=Arc[n,i];
   Visited[i]=0;
}//第n个顶点被访问，因为第n个顶点是开始点
Visited[n]=1;
//找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。
//相当于寻找u点，这个点不是开始点n
for(i=0;i<VerNum;i++)
{
   u=0;
   MinDis=No;
   for(j=0;j<VerNum;j++)
    if(Visited[j] == 0&&(Distance[j]<MinDis))
    {
     MinDis=Distance[j];
     u=j;
    }
//如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2
//找完了，MinDis等于不连接，则返回。这种情况类似V5。
   if(MinDis==No) return ;
//确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。
   Visited[u]=1;
//寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。
//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：
//如果(Distance[u] + Arc[u,j]) <= Distance[j] 则：
//Distance[j] = Distance[u] + Arc[u, j]；
//而iPath[]保存了u点的编号；
//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3
   for(j=0;j<VerNum;j++)
    if(Visited[j]==0&&Arc[u,j]<No&&u!= j) 
    {
     if ((Distance[u] + Arc[u,j]) <= Distance[j])
     {
      Distance[j] = Distance[u] + Arc[u, j];
      Visited[j]=0;
      iPath[j] = u;
     }
    }
}
}

//辅助函数

void Prim()
{
int i,m,n=0;
for(i=0;i<VerNum;i++) 
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
}
Visited[n]++;
listBox1.Items.Add (V[n]); 
while(Visit()>0)
{
   if((m=MinAdjNode(n))!=-1)
   {
    T[n].Nodes.Add(T[m]); 
    n=m;
    Visited[n]++;
   }
   else
   {
    n=MinNode(0);
    if(n>0) T[Min2].Nodes.Add(T[Min1]); 
    Visited[n]++;
   }
   listBox1.Items.Add (V[n]); 
}
treeView1.Nodes.Add(T[0]); 
}
void TopoSort()
{
int i,n;
listBox1.Items.Clear(); 
Stack S=new Stack();
for(i=0;i<VerNum;i++)
   Visited[i]=0;
for(i=VerNum-1;i>=0;i--)
   if(InDegree(i)==0)
   {
    S.Push(i);
    Visited[i]++;
   }
while(S.Count!=0)
{
   n=(int )S.Pop();
   listBox1.Items.Add (V[n]); 
   ClearLink(n);
   for(i=VerNum-1;i>=0;i--)
    if(Visited[i]==0&&InDegree(i)==0)
    {
     S.Push(i);
     Visited[i]++;
    }
}
}
void AOETrave(int n,TreeNode TR,int w)
{
int i,w0;
if(OutDegree(n)==0) return;
for(i=0;i<VerNum;i++)
   if((w0=Arc[n,i])!=0)
   {
    listBox1.Items.Add (V[i]+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());
    TreeNode T1=new TreeNode();
    T1.Text =V[i]+" [W="+(w+w0).ToString()+"]"; 
    TR.Nodes.Add(T1); 
    AOETrave(i,T1,w+w0);
   }
}
void AOE()
{
int i,w=0,m=1;
TreeNode T1=new TreeNode();
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
}
T1.Text =V[0];
listBox1.Items.Add ("双亲表示法显示这个生成树："); 
listBox1.Items.Add ("V\tW\tID\tPID");
for(i=0;i<VerNum;i++)
{
   if((w=Arc[0,i])!=0)
   {
    listBox1.Items.Add (V[i]+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");
    TreeNode T2=new TreeNode();
    T2.Text=V[i]+" [W="+w.ToString()+"]";
    AOETrave(i,T2,w);
    T1.Nodes.Add (T2); 
    listBox1.Items.Add("\t\t树"+m.ToString());
    m++;
   }
}
treeView1.Nodes.Clear(); 
treeView1.Nodes.Add (T1);
}
int IsZero()
{
int i;
for(i=0;i<VerNum;i++)
   if(LineIsZero(i)>=0) return i;
return -1;
}
int LineIsZero(int n)
{
int i;
for(i=0;i<VerNum;i++)
   if (Arc[n,i]!=0) return i;
return -1;
}
void DepthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
   R[i]=0;
}
while((m=IsZero())>=0)
{
   if(Visited[m]==0) 
   {
    listBox1.Items.Add (V[m]);
    R[m]=1;
   }
   Visited[m]++;
   DTrave(m);
}
for(i=0;i<VerNum;i++)
{
   if(R[i]==1)
    treeView1.Nodes.Add (T[i]); 
}
}
void DTrave(int n)
{
int i;
if (LineIsZero(n)<0) return;
for(i=VerNum-1;i>=0;i--)
   if(Arc[n,i]!=0)
   {
    Arc[n,i]=0;
    Arc[i,n]=0;
    if(Visited[i]==0)
    {
     listBox1.Items.Add (V[i]);
     T[n].Nodes.Add (T[i]); 
     R[i]=0;
    }
    Visited[i]++;
    DTrave(i);
   }
}
void BreadthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
   Visited[i]=0;
   T[i]=new TreeNode();
   T[i].Text =V[i];
   R[i]=0;
}
while((m=IsZero())>=0)
{
   if(Visited[m]==0) 
   {
    listBox1.Items.Add (V[m]);
    R[m]=1;
   }
   Visited[m]++;
   BTrave(m);
}
   for(i=0;i<VerNum;i++)
{
   if(R[i]==1)
    treeView1.Nodes.Add (T[i]); 
}
}
void BTrave(int n)
{
int i;
Queue Q=new Queue();
Q.Enqueue(n);
while(Q.Count!=0)
{
   for(i=0;i<VerNum;i++)
   {
    if(Arc[n,i]!=0)
    {
     Arc[n,i]=0;
     Arc[i,n]=0;
     if(Visited[i]==0)
     {
      listBox1.Items.Add(V[i]); 
      T[n].Nodes.Add (T[i]); 
      R[i]=0;
     }
     Visited[i]++;
     Q.Enqueue(i);
    }
   }
   n=(int )Q.Dequeue(); 
}
}
int MinNode(int vn)
{
int i,j,n,m,Min=No;
n=-1;m=-1;
for (i=vn;i<VerNum;i++)
   for(j=0;j<VerNum;j++)
    if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited[i]==0&&Visited[j]==1)
    {
     Min=Arc[i,j];n=i;m=j;
    }
Min1=n;Min2=m;
return n;
}
int MinAdjNode(int n)
{
int i,Min,m;
Min=No;m=-1;
for(i=0;i<VerNum;i++)
   if(Arc[n,i]!=No&&Visited[i]==0&&Min>Arc[n,i]&&Visited[n]==1)
   {
    Min=Arc[n,i];m=i;
   }
return m;
}
int Visit()
{
int i,s=0;
for(i=0;i<VerNum;i++)
   if(Visited[i]==0) s++;
return s;
}