关于最短路问题！！

Question

随便说个事例，用图来编就可以了

Answer 1

真想帮你，可是没时间，给你一个MAPLE代码，先研究一下吧：
Dijkstra:=proc(G,v)
> local Tree,nodes,preV,Dj,V,V_G,
>       i,k,temp2,temp1,tempE,ename,head;
> 
> if (not type(G,GRAPH)) then 
>     error "the parameter must be type of GRAPH" 
> fi:
> 
> nodes:=nops(vertices(G)):
> new(Tree):
> V:=[]:
> V_G:=convert(vertices(G) minus {v},list):
> preV:=table([seq(V_G[i]=v,i=1..nodes-1)]):
> 
> Dj:=table([seq(V_G[i]=infinity,i=1..nodes-1)]):
> for i to nodes-1 do
>     if(edges([v,V_G[i]],G)<>{}) then
>        Dj[V_G[i]]:=eweight(op(edges([v,V_G[i]],G)),G):print(Dj);
>     end if:
> end do:
> 
> for k to nodes-1 do
> temp1:=Dj[V_G[1]];temp2:=1;
> for i to nops(V_G) do
>     if (temp1<Dj[V_G[i]]) then
>        temp1:=Dj[V_G[i]]:
>        temp2:=i:
>     end if:
> end do:
> V:=[op(V),V_G[temp2]]:
> V_G:=[seq(V_G[i],i=1..temp2-1),seq(V_G[i],i=temp2+1..nops(V_G))]:
> for i to nops(V_G) do
>     tempE:=edges([v,V_G[i]],G):
>     if (tempE<>{}) then
>         if(temp1+eweight(op(tempE),G)<Dj[V_G[i]]) then
>             Dj[V_G[i]]:=temp1+eweight(op(tempE),G):
>             preV[V_G[i]]:=V_G[temp2]:
>         end if
>     end if:
> end do:
> if(nargs=3 and ({args[3]} minus vertices(G))={})then
>   if(V[nops(V)]=args[3])then break fi
> end if:
> end do:
> addvertex(vertices(G),Tree):
> if (nargs>=3) then
>   if (({args[3]} minus vertices(G))={}) then
>      head:=args[3]:
>     while(head<>v)do
>      addedge({head,preV[head]},Tree):
>      head:=preV[head]:
>     end do:
>     return Tree:
>   elif (nargs=4) then
>     assign(args[4]=op(Dj)): 
>   else
>     assign(args[3]=op(Dj));
>   end if:
>  end if:
> for i from nodes-1 by -1 to 1 do
> ename:=op(edges([preV[V[i]],V[i]],G)):
> addedge({V[i],preV[V[i]]},names=ename,weights=eweight(ename,G),Tree):
> end do:
> return Tree:
> end proc: