dijkstra演算法c
1. 用C或C++實現求最短路徑的Dijkstra演算法
/* 用鄰接矩陣表示的圖的Dijkstra演算法的源程序*/
#include<stdio.h>
#define MAXVEX 100
typedef char VexType;
typedef float AdjType;
typedef struct
{ VexType vexs[MAXVEX]; /* 頂點信息 */
AdjType arcs[MAXVEX][MAXVEX]; /* 邊信息 */
int n; /* 圖的頂點個數 */
}GraphMatrix;
GraphMatrix graph;
typedef struct {
VexType vertex; /* 頂點信息 */
AdjType length; /* 最短路徑長度 */
int prevex; /* 從v0到達vi(i=1,2,…n-1)的最短路徑上vi的前趨頂點 */
}Path;
Path dist[6]; /* n為圖中頂點個數*/
#define MAX 1e+8
void init(GraphMatrix* pgraph, Path dist[])
{
int i; dist[0].length=0; dist[0].prevex=0;
dist[0].vertex=pgraph->vexs[0];
pgraph->arcs[0][0]=1; /* 表示頂點v0在集合U中 */
for(i=1; i<pgraph->n; i++) /* 初始化集合V-U中頂點的距離值 */
{ dist[i].length=pgraph->arcs[0][i];
dist[i].vertex=pgraph->vexs[i];
if(dist[i].length!=MAX)
dist[i].prevex=0;
else dist[i].prevex= -1;
}
}
void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvex; AdjType min;
init(&graph,dist); /* 初始化，此時集合U中只有頂點v0*/
for(i=1; i<graph.n; i++)
{ min=MAX; minvex=0;
for(j=1; j<graph.n; j++)
if( (graph.arcs[j][j]==0) && (dist[j].length<min) ) /*在V-U中選出距離值最小頂點*/
{ min=dist[j].length; minvex=j; }
if(minvex==0) break; /* 從v0沒有路徑可以通往集合V-U中的頂點 */
graph.arcs[minvex][minvex]=1; /* 集合V-U中路徑最小的頂點為minvex */
for(j=1; j<graph.n; j++) /* 調整集合V-U中的頂點的最短路徑 */
{ if(graph.arcs[j][j]==1) continue;
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
dist[j].prevex=minvex;
}
}
}
}
void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}
int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
}
}
}
void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}
int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
這個稍作改動就可以了。
2. c語言：迪傑斯特拉演算法怎麼看
下面是一道dijkstra的代碼，題目在最下面。
每句解釋很詳細。
#include <stdio.h>
int a[205][205]; //記錄鄰接矩陣
int dist[205]; //到每個點的最短路
int m,n; //m條路，n個點
const int INF=0xfffffff;
void init() //初始化各點間距離
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j]=(i==j?0:INF);
}
void dijkstra(int u) //從第u個點開始走
{
int sign[205]={0}; //標記走過否
int x=u;
int i,j;
for(i=0;i<n;i++) //初始化u到各點距離
dist[i]=a[x][i];
dist[x]=0;
sign[x]=1;
for(i=1;i<=n-2;i++) //找u到各點距離中的最小值
{
int min=INF;
for(j=0;j<n;j++)
{
if(!sign[j] && min>dist[j])
{
min=dist[j];
x=j;
}
}
sign[x]=1;
for(j=0;j<n;j++) //初始化x到各點間距離
{
if(!sign[j] && dist[x]+a[x][j]<dist[j] && a[x][j]<INF)
dist[j]=a[x][j]+dist[x];
}
}
}
int main()
{
int i;
while(scanf("%d %d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if(z<a[x][y])
a[x][y]=z;
if(z<a[y][x])
a[y][x]=z;
}
int s,t;
scanf("%d %d",&s,&t);
dijkstra(s);
if(dist[t]<2000000)
printf("%d\n",dist[t]);
else
printf("-1\n");
}
return 0;
}
/*
本題目包含多組數據，請處理到文件結束。
每組數據第一行包含兩個正整數N和M(0<N<200,0<M<1000)，分別代表現有城鎮的數目和已修建的道路的數目。城鎮分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。
再接下一行有兩個整數S,T(0<=S,T<N)，分別代表起點和終點。
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
*/
3. 最短路徑演算法 Dijkstra 用C語言編出來
#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT 3//定義最大的頂點數目
#define limit 32767 //設置沒有路徑的權代替無窮大
struct record{ //沒個頂點的數據結構設置為一個數組隊列
int number; //頂點號
int flag; //標志是否從隊列中被選過如果為1表示選過為0表示未選
int allpath; //從源點到這個點的當前最短距離（權最小）
}path[MAXPOINT+1];
int cost[MAXPOINT+1][MAXPOINT+1]; //用來表示圖的鄰接矩陣
void main()
{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在數組隊列中的當前下標 front表示隊列首 rear表示隊列尾
//N 表示待輸入的源點號碼 minnumber 表示選中的點的號碼
int min=32768; //設置一個初始值
for(i=1;i<=MAXPOINT;i++)
for(j=1;j<=MAXPOINT;j++)
{cout<<"請輸入從第"<<i<<"點到第"<<j<<"點的路徑長度(權)如果沒有路徑的話請輸入'32767' "<<endl;
cin>>cost[i][j]; //初始化所有點之間的（權）路徑值
}
//cout<<"請輸入源點號"<<endl; //輸入一個起點
//cin>>N;
for(N=MAXPOINT;N>=1;N--)//把每一個點輪流地都設置為起點，可以求出任意一對頂點之間的最短路徑
{ for(i=front;i<=rear;i++) //初始化每個點的信息
{if(i==N)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}
while(rear>=1) //控制循環次數
{for(temp=front;temp<=MAXPOINT;temp++)
{ if(path[temp].allpath<min&&path[temp].flag==0)//選出一個具有最值
//的點
{ minnumber=path[temp].number;
min=path[temp].allpath ;
}
}
min=32768;
path[minnumber].flag=1;//把選中的點的標志變數置1表示已經被選過避免選中
for(i=1;i<=MAXPOINT;i++)//進行類似廣度優先搜索，更新最短路徑
{if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
}
rear--;//次數減1
}
rear=MAXPOINT; //恢復數組以便於下一點的循環
for(j=1;j<=MAXPOINT;j++)
{ cout<<"第"<<N<<"點到第"<<j<<"點的最短路徑長度（權）為";
cout<<path[j].allpath <<endl;
}
}
}
//這個程序可以求出任意一對頂點之間的最短路徑，不過這種演算法效率還不是很高，還有其他演算法待續
4. 用Dijkstra演算法的基本思路並且是用C語言編寫出求最小路徑的代碼
Dijkstra演算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等於零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑演算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：
dj=min［dj, dk+lkj］
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min［dj, 所有未標記的點j］
點i就被選為最短路徑中的一點，並設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：
i=j*
5) 標記點i。如果所有點已標記，則演算法完全推出，否則，記k=i，轉到2) 再繼續。
#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 無窮大 */
#define N 20 /* 城市頂點的數目 */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存儲當前最短路徑長度 */
int v0 = 'A' - 65; /* 初始點是 A */
void main()
{
int final[N], i, v, w, min;
/* 初始化最短路徑長度數據，所有數據都不是最終數據 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* 首先選v0到v0的距離一定最短，最終數據 */
final[v0] = true;
/* 尋找另外 N-1 個結點 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短長度無窮大 */
/* 尋找最短的邊 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新邊 */
for (w = 0; w < N; w++) { /* 更新 dist[] 數據 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* 顯示到監視器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
}
5. 關於Dijkstra演算法
樓上正解，你找個圖自己用此演算法實踐一下就知道了，從A點出發，發現離A最近的點是B點，那麼我們就已經認為A到B的最短距離就是AB了，如果有負數，就指不定冒出個C點,AC+CB<AB;或者冒出個DE為很大的負值，AC+CD+DE+EF+FB<AB;等等諸如此類的情況。
簡單說來，你駕車從家出發到某地沿某條路只需經過一個收費站，但是遠在外省某地有個站不但不收你的費，你去了還會給你個千八百萬的歡迎光臨費，你能說你直接沿著這條路去某地是最省費用的？不計時間成本，繞到外省那個給你錢的地方，再繞回到你的目的地，還能賺錢呢。
而且一般權值為負的圖研究也比較少。有些帶負權的圖，某些點間還沒有最小距離呢。中間出個帶某條負權很大的邊的環圈，繞此一圈所經過的距離反而減少了，那就一直在此圈上繞啊繞啊繞到負的足夠大溢出為止。
當然考慮各種自己隨便假設出來的變種問題也是很有趣的。比如說邊帶有多個權值對應多次經過改變的消費，上面的問題有可能變成有解的。話說那個站會後悔，第二次經過它會收回100萬，第三次經過收回250萬，這樣的話你只需要經過一次就夠了，問題也是有解的。再比如說對於多權重圖，從A點出發經過B點到達C點的最短路線，就不是簡單的AB最短路線+BC最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^
6. Dijkstra演算法的原理和C的編程實現
.Dijkstra演算法求單源最短路徑
語法：result=Dijkstra(Graph G,int n,int s,int t, int path[]);
參數：
G：
圖，用鄰接矩陣表示
n：
圖的頂點個數
s：
開始節點
t：
目標節點
path[]：
用於返回由開始節點到目標節點的路徑
返回值：
最短路徑長度
注意：
輸入的圖的權必須非負
頂點標號從0開始
用如下方法列印路徑：
i=t;
while (i!=s)
{
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
源程序：
int Dijkstra(Graph G,int n,int s,int t, int path[])
{
int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
for (i=0;i<n;i++) mark[i]=0;
for (i=0;i<n;i++)
{ d[i]=G[s][i];
path[i]=s; }
mark[s]=1;path[s]=0;d[s]=0;
for (i=1;i<n;i++)
{
minc=infinity;
w=0;
for (j=0;j<n;j++)
if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
mark[w]=1;
for (j=0;j<n;j++)
if ((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{ d[j]=d[w]+G[w][j];
path[j]=w; }
}
return d[t];
}
原理：（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ∞(若u不是v的出邊鄰接點）。 （2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。 （3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值為頂點k的距離加上邊上的權。 （4）重復步驟（2）和（3）直到所有頂點都包含在S中。
7. C語言實現Dijkstra演算法
#include<stdlib.h> #define INFINITY 1000000000 //最大距離
#define MAX_NODES 1024 //最大節點數
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示從 i 到 j 的距離 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驅節點
int length; //到起始點的距離
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是當前工作節點
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}
8. 用dijkstra演算法解決最短路徑問題c語言代碼實現時怎樣將每一個路徑的頂點次序依次輸出出來
dijkstra演算法原理主要就是已知源節點（v）和n個節點間代價函數（有向網路矩陣cost），通過不斷將節點加入到一個節點子集S中，使得經過加入S後的各節點的路徑代價是最小的，直至S節點包含了所有的n個節點停止。（具體演算法闡明網上很多資料）。閑話少說，直接附程序吧～
/*
readme:
first,you need to input the node number, the cost matrix and the source node;
then the program will compute the best path.
finally,the program will output the lowest distance to the destination node, the pre-node and show the best path.
*/
＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra演算法實現函數
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值
int *s ;//定義具有最短路徑的節點子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路徑代價和前一跳節點值
for (i = 1; i <= n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源節點作為最初的s子集
for (i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代價的鄰居節點到s子集
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//計算加入新的節點後，更新路徑使得其產生代價最短
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (cost[u][j] < maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路徑函數
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路徑
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//輸出路徑
printf("the best path is:\n");
for (j = count; j >= 1; j--)
{
printf("%d -> ",way[j]);
}
printf("%d\n",u);
}
//主函數，主要做輸入輸出工作
void main()
{
int i,j,t;
int n,v,u;
int **cost;//代價矩陣
int *dist;//最短路徑代價
int *prev;//前一跳節點空間
printf("please input the node number: ");
scanf("%d",&n);
printf("please input the cost status:\n");
cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i <= n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//輸入代價矩陣
for (j = 1; j <= n; j++)
{
for (t = 1; t <= n; t++)
{
scanf("%d",&cost[j][t]);
}
}
dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf("please input the source node: ");
scanf("%d",&v);
//調用dijkstra演算法
Dijkstra(n, v, dist, prev, cost);
printf("*****************************\n");
printf("have confirm the best path\n");
printf("*****************************\n");
for(i = 1; i <= n ; i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]);
printf("the pre-node of node %d is node %d \n",i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}
9. 求Dijkstra演算法的C語言實現
//Dijkstra演算法 C語言實現 2008-08-26 12:07 #include<stdio.h>
#include<stdlib.h> #define INFINITY 1000000000 //最大距離
#define MAX_NODES 1024 //最大節點數
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示從 i 到 j 的距離 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驅節點
int length; //到起始點的距離
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是當前工作節點
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}
10. Dijkstra演算法的C語言實現：文件讀取、圖的存儲、演算法實現、路徑輸出
要現寫，你的分太少了，至少也200分吧，我給你個模板，時間復雜度為nLOG2(n)：
dij鄰接陣
#include <algorithm>
#include <deque>
#include <queue>
#include <iostream>
using namespace std;
#define MN 1001
#define INF (1<<29)
int graf[MN][MN];
struct node
{
int v;
int dis;
node(int vv,int dd){v=vv;dis=dd;}
node(){}
};
bool operator < (const node aa,const node bb)
{
return aa.dis>bb.dis;//最小堆
}
int dis[MN];
void dijkstra(int s,int n)//s是源點,[1..n]
{
node tmp;
int i,w;
for(i=1;i<=n;++i){dis[i]=INF;}
priority_queue < node,deque<node> > Q;
Q.push(node(s,0));
for(dis[s]=0;!Q.empty();)
{
tmp=Q.top();Q.pop();
if(tmp.dis!=dis[tmp.v])continue;
for(i=1;i<=n;++i)
{
w=graf[tmp.v][i];
if(w!=INF&&dis[tmp.v]+w<dis[i])
{
//必要時可保存路徑pre[i]=tmp.v
dis[i]=dis[tmp.v]+w;
Q.push(node(i,dis[i]));
}
}
}
}