问基于成本和质量的dijkstras改进

EN

dijs<-function(n,v,cost,dist)
{

 dist<-numeric(n)  
 flag<- numeric(n)
 prev<-numeric(n)

 for(i in 1:n)
  prev[i] = -1

for(i in 1:n)
dist[i]<-cost[v,i]

count=2
while(count <= n)
{
  min=999
  for(w in 1:n)
  {     
    if(dist[w] < min && !flag[w])
    {
      min=dist[w]
      u=w
    }
  }
  flag[u]=1
  count<-count+1
  for(w in 1:n)
  {
    if((dist[u]+cost[u,w] < dist[w]) && !flag[w])
    {
      dist[w]=dist[u]+cost[u,w]
      prev[w]=u
    }


  }
}

  printmin(v,dist,n)
   return(prev)
}

main<-function()
{
  cat('Enter no of nodes:', '\n')

  n<-scan("",n=1,quiet=TRUE)
  cat('Enter cost matrix','\n')
  cost<-matrix(0,n,n)
  for(i in 1:n) for(j in 1:n) 
  {
    if(i == j)
      cost[i,j]<-999

    if(i != j && cost[i,j] == 0)
    {
      cat(sprintf("enter the cost from node %d to %d",i,j))
      cost[i,j]<-scan("",n=1,quiet=TRUE)
      if(cost[i,j] == 0)
        cost[i,j]=999
      cost[j,i]<-cost[i,j]
    }


  }

  print(cost)

  print('Enter the source:',quote=FALSE) 
  v<-scan("",n=1,quiet=TRUE)

  prev<-digs(n,v,cost,dest)
  print("the shortest distance")

  for(i in 1:n)
  {
    cat(sprintf("path to %d ->",i))

    printpath(i,prev)
    cat('\n')
  }

}
printmin<-function(v,mindist,n)
{
  for(i in 1:n)
  {
     if(i != v)
     {
       cat(sprintf("%d -> %d, cost =%f",v,i,mindist[i]))
       cat('\n')

     }
  }
}


 printpath<-function(dest,prev)
 {
   if(prev[dest] != -1)
    printpath(prev[dest],prev)
  cat(sprintf("%d  ",dest))

 }