最小路徑問題 | Dijkstra算法詳解（附代碼）

#include"Dijkstra.h"
//構(gòu)造函數(shù)Graph_DG::Graph_DG(int vexnum, int edge) {    //初始化頂點數(shù)和邊數(shù)    this->vexnum = vexnum;    this->edge = edge;    //為鄰接矩陣開辟空間和賦初值    arc = new int*[this->vexnum];    dis = new Dis[this->vexnum];    for (int i = 0; i < this->vexnum; i++) {        arc[i] = new int[this->vexnum];        for (int k = 0; k < this->vexnum; k++) {            //鄰接矩陣初始化為無窮大                arc[i][k] = INT_MAX;        }    }}//析構(gòu)函數(shù)Graph_DG::~Graph_DG() {    delete[] dis;    for (int i = 0; i < this->vexnum; i++) {        delete this->arc[i];    }    delete arc;}
// 判斷我們每次輸入的的邊的信息是否合法//頂點從1開始編號bool Graph_DG::check_edge_value(int start, int end, int weight) {    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {        return false;    }    return true;}
void Graph_DG::createGraph() {    cout << "請輸入每條邊的起點和終點（頂點編號從1開始）以及其權(quán)重" << endl;    int start;    int end;    int weight;    int count = 0;    while (count != this->edge) {        cin >> start >> end >> weight;        //首先判斷邊的信息是否合法        while (!this->check_edge_value(start, end, weight)) {            cout << "輸入的邊的信息不合法，請重新輸入" << endl;            cin >> start >> end >> weight;        }        //對鄰接矩陣對應(yīng)上的點賦值        arc[start - 1][end - 1] = weight;        //無向圖添加上這行代碼        //arc[end - 1][start - 1] = weight;        ++count;    }}
void Graph_DG::print() {    cout << "圖的鄰接矩陣為：" << endl;    int count_row = 0; //打印行的標(biāo)簽    int count_col = 0; //打印列的標(biāo)簽    //開始打印    while (count_row != this->vexnum) {        count_col = 0;        while (count_col != this->vexnum) {            if (arc[count_row][count_col] == INT_MAX)                cout << "∞" << " ";            else            cout << arc[count_row][count_col] << " ";            ++count_col;        }        cout << endl;        ++count_row;    }}void Graph_DG::Dijkstra(int begin){    //首先初始化我們的dis數(shù)組    int i;    for (i = 0; i < this->vexnum; i++) {        //設(shè)置當(dāng)前的路徑        dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);        dis[i].value = arc[begin - 1][i];    }    //設(shè)置起點的到起點的路徑為0    dis[begin - 1].value = 0;    dis[begin - 1].visit = true;
    int count = 1;    //計算剩余的頂點的最短路徑（剩余this->vexnum-1個頂點）    while (count != this->vexnum) {        //temp用于保存當(dāng)前dis數(shù)組中最小的那個下標(biāo)        //min記錄的當(dāng)前的最小值        int temp=0;        int min = INT_MAX;        for (i = 0; i < this->vexnum; i++) {            if (!dis[i].visit && dis[i].value                min = dis[i].value;                temp = i;            }        }        //cout << temp + 1 << "  "<        //把temp對應(yīng)的頂點加入到已經(jīng)找到的最短路徑的集合中        dis[temp].visit = true;        ++count;        for (i = 0; i < this->vexnum; i++) {            //注意這里的條件arc[temp][i]!=INT_MAX必須加，不然會出現(xiàn)溢出，從而造成程序異常            if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {                //如果新得到的邊可以影響其他為訪問的頂點，那就就更新它的最短路徑和長度                dis[i].value = dis[temp].value + arc[temp][i];                dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);            }        }    }
}void Graph_DG::print_path(int begin) {    string str;    str = "v" + to_string(begin);    cout << "以"<"為起點的圖的最短路徑為：" << endl;    for (int i = 0; i != this->vexnum; i++) {        if(dis[i].value!=INT_MAX)        cout << dis[i].path << "=" << dis[i].value << endl;        else {            cout << dis[i].path << "是無最短路徑的" << endl;        }    }}

#include"Dijkstra.h"
//檢驗輸入邊數(shù)和頂點數(shù)的值是否有效，可以自己推算為啥：//頂點數(shù)和邊數(shù)的關(guān)系是：((Vexnum*(Vexnum - 1)) / 2) < edgebool check(int Vexnum, int edge) {    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)        return false;    return true;}int main() {    int vexnum; int edge;
    cout << "輸入圖的頂點個數(shù)和邊的條數(shù)：" << endl;    cin >> vexnum >> edge;    while (!check(vexnum, edge)) {        cout << "輸入的數(shù)值不合法，請重新輸入" << endl;        cin >> vexnum >> edge;    }    Graph_DG graph(vexnum, edge);    graph.createGraph();    graph.print();    graph.Dijkstra(1);    graph.print_path(1);    system("pause");    return 0;}