dijkstra演算法c代碼
❶ 用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]);
}
}
❷ c語言問題.
Dijkstra演算法可描述如下:
1初始化： S ← { v0 };
dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
// n為圖中頂點個數
2求出最短路徑的長度：
dist[k] ← min{ dist[i] }, i V- S ;
S ← S U { k };
3修改：
dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },
對於每一個 i V- S ;
4判斷： 若S = V, 則演算法結束，否則轉2。
用於計算最短路徑的圖鄰接矩陣類的定義
const int NumVertices = 6; //圖中最大頂點個數
class Graph { //圖的類定義
private:
int Edge[NumVertices][NumVertices]; //鄰接矩陣
int dist[NumVertices]; //最短路徑長度數組
int path[NumVertices]; //最短路徑數組
int S[NumVertices]; //最短路徑頂點集
public:
void ShortestPath ( const int, const int );
int choose ( const int );
};
計算從單個頂點到其它各個頂點的最短路徑
void Graph::ShortestPath ( const int n, const int v ){
//Graph是一個具有n個頂點的帶權有向圖, 各邊上
//的權值由Edge[i][j]給出。本演算法建立起一個數
//組: dist[j], 0 j < n, 是當前求到的從頂點v到頂點
//j的最短路徑長度, 同時用數組path[j], 0 j < n, 存
//放求到的最短路徑。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist數組初始化
S[i] = 0;
if ( i != v && dist[i] < MAXINT ) path[i] = v;
else path[i] = -1; //path數組初始化
}
S[v] = 1; dist[v] = 0; //頂點v加入頂點集合
//選擇當前不在集合S中具有最短路徑的頂點u
for ( i = 0; i < n-1; i++ ) {
int min = MAXINT; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //將頂點u加入集合S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXINT &&
dist[u] + Edge[u][w] < dist[w] ) {
dist[w] = dist[u] + Edge[u][w];
path[w] = u;
}
Floyd演算法的基本思想：
定義一個n階方陣序列：
A(-1), A(0), …, A(n-1).
其中 A(-1) [i][j] = Edge[i][j]；
A(k) [i][j] = min { A(k-1)[i][j]，
A(k-1)[i][k] + A(k-1)[k][j] }, k = 0,1,…, n-1
A(0) [i][j]是從頂點vi 到vj , 中間頂點是v0的最短路徑的長度, A(k) [i][j]是從頂點vi 到vj , 中間頂點的序號不大於k的最短路徑的長度, A(n-1)[i][j]是從頂點vi 到vj 的最短路徑長度。
所有各對頂點之間的最短路徑
void Graph::AllLengths ( const int n ) {
//Edge[n][n]是一個具有n個頂點的圖的鄰接矩陣。//a[i][j]是頂點 i 和 j 之間的最短路徑長度。path[i][j]
//是相應路徑上頂點 j 的前一頂點的頂點號, 在求
//最短路徑時圖的類定義中要修改path為
//path[NumVertices][NumVertices]。
for ( int i = 0; i < n; i++ ) //矩陣a與path初始化
for ( int j = 0; j < n; j++ ) {
a[i][j] = Edge[i][j];
if ( i <> j && a[i][j] < MAXINT )
path[i][j] = i; // i 到 j 有路徑
else path[i][j] = 0; // i 到 j 無路徑
}
for ( int k = 0; k < n; k++ ) //產生a(k)及path(k)
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
if ( a[i][k] + a[k][j] < a[i][j] ) {
a[i][j] = a[i][k] + a[k][j];
path[i][j] = path[k][j];
} //縮短路徑長度, 繞過 k 到 j
}
❸ 最短路徑演算法 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;
}
}
}
//這個程序可以求出任意一對頂點之間的最短路徑，不過這種演算法效率還不是很高，還有其他演算法待續
❹ 怎麼用c語言實現單源最短路徑問題要求是用Dijkstra演算法，最好寫出所有的代碼 ，包括結構定義等等，對一
C語言代碼：//清華大學出版社光碟的代碼
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 演算法7.15
// 用Dijkstra演算法求有向網G的v0頂點到其餘頂點v的最短路徑P[v]
// 及其帶權長度D[v]。
// 若P[v][w]為TRUE，則w是衡辯嘩灶賀從v0到v當前求得最短路徑上的頂點。
// final[v]為TRUE當且僅當v∈S,即已經求得從v0到v的最短路徑。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 設空路徑
if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0頂點屬於S集
//--- 開始主循環，每次求得v0到某個v頂點的最短路徑，並加v到S集 ---
for (i=1; i<G.vexnum; ++i) { // 其餘G.vexnum-1個頂點
min = INFINITY; // 當前所知離v0頂點的最近距離
for (w=0; w<G.vexnum; ++w)
if (!final[w]) // w頂點在V-S中
if (D[w]<min) { v = w; min = D[w]; } // w頂點離v0頂點更近
final[v] = TRUE; // 離v0頂點最近的咐行v加入S集
for (w=0; w<G.vexnum; ++w) // 更新當前最短路徑及距離
if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行賦值於第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ
❺ 用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);
}
}
}
❻ 用Matlab/C實現基於Dijkstra的路由選擇演算法實現
/**************************************************************
* 給定一個帶權有向圖G = (V，E)，其中每條邊的權是一個非負整數。*
* 另外還給定V中的一個頂點，稱為源。現在我們要計算從源到所有其 *
* 他各頂點的最短路長度。這里路徑長度是路上各邊權之和。這個問 *
* 題通常稱為單源最短路徑問題。 *
***************************************************************/
#include<iostream.h>
#define INFINITE 100
void main()
{
int j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];
for(i = 0; i < n; i++)
{
w[i] = new int[n];
}
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cin>>w[i][j];
for(s[0] = 1,i = 1; i < n; i++)
{
s[i] = 0;
d[i] = w[0][i];
if(d[i] < INFINITE)
p[i]=0;
else
p[i]=-1;
}
for(i = 1; i < n; i++)
{
t = INFINITE;
k = 1;
for(j = 1; j < n; j++)
if((!s[j]) && (d[j] < t))
{
t = d[j];
k = j;
}
s[k]=1;//point k join the S
for (j = 1; j < n; j++)
if((!s[j]) && (d[j] > d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j];
p[j] = k;
}
}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
cout<<endl;
}
/*********
頂點個數用n表示，這里給出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具體例子見 電子工業出版社 《演算法設計技巧與分析》148頁
************/
❼ 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中。
❽ 用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;
}
這個稍作改動就可以了。