一 、目的：
1.掌握最短路徑算法的基本原理及編程實現；
二 、環(huán)境：
operating system version：Win11
CPU instruction set: ?x64
Integrated Development Environment：Viusal Studio 2022
三 、內容：
1)建立一張圖，選擇一種存儲結構(鄰接矩陣或鄰接表)初始化該圖；
2)用Dijkstra算法實現點與點之間的最短路徑。
四 、要求：
1) 實現圖的兩種表示方法；
2) 實現Dijkstra算法；
五 、步驟：
1. 程序：
?
#include<iostream>
#define MVNum 100
#define MaxInt 32767 //極大值，即∞
using namespace std;
typedef int ArcType;
typedef char VerTextType[20];
int* D = new int[MVNum];
bool* S = new bool[MVNum];
int* Path = new int[MVNum];
typedef struct ArcNode //邊結點
{
int adjver; //該邊所指向的頂點位置
struct ArcNode* nextarc; //指向下一條邊的指針
ArcType weight;
} ArcNode;
typedef struct VNode //頂點信息
{
VerTextType data;
ArcNode* firstarc;
} VNode, AdjList[MVNum];
typedef struct node
{
AdjList vertices;
int vexnum; //圖的當前頂點數
int arcnum; //圖的當前邊數
} ALGraph;
//臨接表存儲方式最短路徑（dijkstra）,復雜度O(n^2)
void ShortestPath_DIJ2(ALGraph G, int v0, ArcType D[], int Path[])
{
int ok[MVNum], i, j; // ok數組標記是否確定最短路徑
for (i = 0; i < G.vexnum; i++) {
ok[i] = 0;
Path[i] = -1;
D[i] = MaxInt;
}
D[v0] = 0;
for (i = 0; i < G.vexnum; i++) {
int min_node = -1;
for (j = 0; j < G.vexnum; j++) {
if (ok[j] == 0 && (min_node == -1 || D[j] < D[min_node])) {
min_node = j;
}
}
if (min_node == -1) break;
ok[min_node] = 1;
ArcNode* cur = G.vertices[min_node].firstarc;
while (cur != NULL) {
if (ok[cur->adjver] == 0 && D[cur->adjver] > D[min_node] + cur->weight) {
D[cur->adjver] = D[min_node] + cur->weight;
Path[cur->adjver] = min_node;
}
cur = cur->nextarc;
}
}
}
//圖的鄰接矩陣
typedef struct
{
char vexs[MVNum]; //頂點表
int arcs[MVNum][MVNum]; //鄰接矩陣
}Graph;
void InitGraph(Graph& G, int vex)
{
cout << "輸入點的名稱，如a" << endl;
for (int i = 0; i < vex; ++i) {
cout << "請輸入第" << (i + 1) << "個點的名稱:";
cin >> G.vexs[i];
}
cout << endl;
for (int i = 0; i < vex; ++i) //初始化鄰接矩陣，邊的權值均置為極大值MaxInt
for (int j = 0; j < vex; ++j)
{
if (j != i)
G.arcs[i][j] = MaxInt;
else
G.arcs[i][j] = 0;
}
}
//確定點v在G中的位置
int LocateVex(Graph G, char v, int vex) {
for (int i = 0; i < vex; ++i)
if (G.vexs[i] == v)
return i;
return -1;
}
//創(chuàng)建無向網G
void CreateUDN(Graph& G, int vex, int arc)
{
int i, j, k;
cout << "輸入邊依附的頂點(node1 node2 weight)" << endl;
for (k = 0; k < arc; ++k) { //構造鄰接矩陣
char v1, v2;
int o;
cout << "請輸入第" << (k + 1) << "條邊依附的頂點和對應的權值:";
cin >> v1 >> v2 >> o;
i = LocateVex(G, v1, vex); j = LocateVex(G, v2, vex);
G.arcs[j][i] = G.arcs[i][j] = o;
}
}
void DisplayGraph(Graph G, int vex)
{
int i, j;
for (i = 0; i < vex; ++i) {
for (j = 0; j < vex; ++j) {
if (G.arcs[i][j] != MaxInt)
cout << G.arcs[i][j] << "\t";
else
cout << "∞" << "\t";
}
cout << endl;
}
}
//用Dijkstra算法求無向網G的v0頂點到其余頂點的最短路徑
void ShortestPath_DIJ(Graph G, int v0, int vex) {
int v, i, w, min;
int n = vex;
for (v = 0; v < n; ++v) {
S[v] = false;
D[v] = G.arcs[v0][v];
if (D[v] < MaxInt) Path[v] = v0;
else Path[v] = -1;
}
S[v0] = true;
D[v0] = 0;
for (i = 1; i < n; ++i) {
min = MaxInt;
for (w = 0; w < n; ++w)
if (!S[w] && D[w] < min) {
v = w;
min = D[w];
}//if
S[v] = true;
for (w = 0; w < n; ++w) //更新從v0出發(fā)到集合V?S上所有頂點的最短路徑長度
if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) {
D[w] = D[v] + G.arcs[v][w]; //更新D[w]
Path[w] = v; //更改w的前驅
}
}
for (int i = 0; i < vex; i++) {
if (D[i] != 0)
if (D[i] != MaxInt)
cout << "到" << G.vexs[i] << "最短路徑長度:" << D[i] << endl;
else
{
cout << "到" << G.vexs[i] << "最短路徑長度:" << "無法到達" << endl;
}
}
}
int main()
{
Graph G;
int vexnum, arcnum;
cout << "請分別輸入總頂點數和總邊數:";
cin >> vexnum >> arcnum;
cout << endl;
InitGraph(G, vexnum);
int v = 0;
CreateUDN(G, vexnum, arcnum);
cout << endl;
cout << "已創(chuàng)建無向圖G" << endl << endl;
DisplayGraph(G, vexnum);
int v0 = LocateVex(G, '0', vexnum);
ShortestPath_DIJ(G, v0, vexnum);
}
2.程序結果：
1）程序運行，我使用的測試數據如下所示：
2）我采用鄰接矩陣的方式實現最短路徑的存儲。創(chuàng)建的無向圖G如下：
3）最終通過Dijkstra算法輸出源點0到其余節(jié)點的最短路徑如下：
六 、小結：
????? ?此次是關于Dijkstra最短路徑算法的編程與實現。我先分別嘗試了采用鄰接矩陣以及鄰接表的存儲結構，比較了他們的優(yōu)缺點：其中圖的鄰接矩陣存儲方式是用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，一個二維數組（鄰接矩陣）存儲圖中的邊或弧的信息。從這個矩陣中，可以較容易知道圖中的信息。1）可以判斷任意兩頂點是否有邊無邊；2）可以知道某個頂點的度，其實就是這個頂點vi在鄰接矩陣中第i行或（第i列）的元素之和；3）求頂點vi的所有鄰接點就是將矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點；而鄰接表則是將圖中頂點用一個一維數組存儲，當然，頂點也可以用單鏈表來存儲。圖中每個頂點vi的所有鄰接點構成一個線性表，由于鄰接點的個數不定，所以，用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表。文章來源：http://www.zghlxwxcb.cn/news/detail-509411.html
????????最終我在構建圖的時候選擇了鄰接矩陣的方式實現。通過鄰接矩陣的Dijkstra時間復雜度是O(N2)。其中每次找到離1號頂點最近的頂點的時間復雜度是 O(N)。整個程序的基本思想是：設置兩個頂點集S和T，集合S中存放已經找到最短路徑的頂點，集合T中存放著當前還未找到最短路徑的頂點；初始狀態(tài)下，集合S中只包含源點V1，T中為除了源點以外的其他頂點，此時源點到各頂點的最短路徑為兩個頂點所連的邊上的權值，若是源點V1到該頂點沒有邊，則最小路徑為無窮大；從集合T中選取到源點V1的路徑長度最短的頂點Vi加入到集合S中；修改源點V1到集合T中剩余頂點Vj的最短路徑長度。新的最短路徑長度值為Vj原來的最短路徑長度值與頂點Vi的最短路徑長度加上Vi到Vj的路徑長度值中的較小者；不斷重復步驟三、4，直至集合T的頂點所有加入到集合S中。文章來源地址http://www.zghlxwxcb.cn/news/detail-509411.html
到了這里，關于最短路徑算法的編程與實現 C語言的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
