Johnson算法「建議收藏」

Jetbrains全家桶1年46，售後保障穩定

C++版:

/************************************************************ 
Johnson.h: Johnson算法，存儲為鄰接表， 
Date: 2014/1/5 
Author: searchop 
************************************************************/  
#ifndef ALGRAPH_H  
#define ALGRAPH_H  
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
//鄰接表的結構  
struct ArcNode          //表結點  
{  
int source;        //圖中該弧的源節點  
int adjvex;        //該弧所指向的頂點的位置  
ArcNode *nextarc;  //指向下一條弧的指針  
int weight;         //每條邊的權重  
};  
template   
struct VertexNode           //頭結點  
{  
VertexType data;    //頂點信息  
ArcNode *firstarc;  //指向第一條依附于該頂點的弧的指針  
int key;            //Prim:保存連接該頂點和樹中結點的所有邊中最小邊的權重;   
//BellmanFord:記錄從源結點到該結點的最短路徑權重的上界  
VertexNode *p;      //指向在樹中的父節點  
int indegree;       //記錄每個頂點的入度  
};  
const int SIZE = 6;  
//圖的操作  
template   
class ALGraph  
{  
public:  
typedef VertexNode VNode;  
ALGraph(int verNum) : vexnum(verNum), arcnum(0)  
{  
for (int i = 0; i < MAX_VERTEX_NUM; i++)  
{  
vertices[i].firstarc = NULL;  
vertices[i].key = INT_MAX/2;  
vertices[i].p = NULL;  
vertices[i].indegree = 0;  
}  
}  
//構造算法導論410頁圖（帶權有向圖）  
void createWDG()  
{  
cout << "構造算法導論410頁圖（帶權有向圖）..." << endl;  
int i;  
for (i = 1; i < vexnum; i++)  
vertices[i].data = 'a' + i - 1;       
insertArc(1, 2, 3);  
insertArc(1, 3, 8);  
insertArc(1, 5, -4);  
insertArc(2, 4, 1);  
insertArc(2, 5, 7);  
insertArc(3, 2, 4);  
insertArc(4, 3, -5);  
insertArc(4, 1, 2);  
insertArc(5, 4, 6);  
}  
void createG()  
{  
cout << "構造圖G'...." << endl;  
vertices[0].data = 's';  
insertArc(0, 1, 0);  
insertArc(0, 2, 0);  
insertArc(0, 3, 0);  
insertArc(0, 4, 0);  
insertArc(0, 5, 0);  
}  
//Johnson算法，先使用BellmanFord算法，使所有的邊的權重變為非負值，  
//然後運用dijkstra算法求出結點對的最短路徑  
int **Johnson()  
{  
createG();          //構造G’  
displayGraph();  
if (!BellmanFord(1))  
cout << "the input graph contains a negative-weight cycle" << endl;  
else  
{  
int h[SIZE];  
int i, j, k;  
//将數組h[]的值設為運行BellmanFord後取得的值，h[i]為結點s到其他點的最短路徑  
for (i = 0; i < vexnum; i++)  
h[i] = vertices[i].key;  
//遍曆所有的邊，将邊的權值重新賦值,即将所有的邊的權值改為負值  
for (i = 0; i < vexnum; i++)  
{  
ArcNode *arc = vertices[i].firstarc;  
for (; arc != NULL; arc = arc->nextarc)  
arc->weight = arc->weight + h[arc->source] - h[arc->adjvex];  
}     
以下為代碼：  
cout << "改變權重後的圖為：" << endl;                                                                                                                     displayGraph();  
int **d = new int *[SIZE];  
for (j = 0; j < SIZE; j++)  
d[j] = new int[SIZE];  
//對每個結點運行dijkstra算法，求出每個點到其他點的最短路徑，保存在key中  
for (k = 1; k < SIZE; k++)  
{  
Dijkstra(k+1);  
for (i = 1; i < SIZE; i++)  
d[k][i] = vertices[i].key + h[i] - h[k];  
}  
cout << "最後計算出的結點對的最短距離：" << endl;  
displayTwoDimArray(d);  
return d;  
}  
}  
//輸出一個二維數組  
void displayTwoDimArray(int **p)  
{  
for (int i = 0; i < SIZE; i++)  
{  
for (int j = 0; j < SIZE; j++)  
cout << p[i][j] << " ";  
cout << endl;  
}  
cout << "~~~~~~~~~~~~~~~" << endl;  
}  
//打印鄰接鍊表  
virtual void displayGraph()  
{  
for (int i = 0; i < vexnum; i++)  
{  
cout << "第" << i+1 << "個頂點是：" << vertices[i].data  
<< " 頂點的入度為：" << vertices[i].indegree << " 鄰接表為: ";  
ArcNode *arcNode = vertices[i].firstarc;  
while (arcNode != NULL)  
{  
cout << " -> " << vertices[arcNode->adjvex].data  
<< "(" << arcNode->weight << ")";  
arcNode = arcNode->nextarc;  
}  
cout << endl;  
}  
cout << "*******************************************************" << endl;  
}  
//PVnode排序準則  
class PVNodeCompare  
{  
public:  
bool operator() (VNode *pvnode1, VNode *pvnode2)  
{  
return pvnode1->key > pvnode2->key;  
}  
};  
//對每個結點的最短路徑估計和前驅結點進行初始化，最短路徑初始化為INT_MAX, p初始化為NULL  
//并将源節點的key初始化為0  
void InitalizeSingleSource(int index)  
{  
for (int i = 0; i < MAX_VERTEX_NUM; i++)  
{  
vertices[i].key = INT_MAX>>2;  
vertices[i].p = NULL;  
}  
vertices[index].key = 0;  
}  
//對邊（u, v）進行松弛，将目前s到v的最短路徑v.key與s到u的最短路徑加上w(u, v)的值進行比較  
//如果比後面的值還大，則進行更新，将v.key縮短，并且将p置為u  
void relax(ArcNode *arc)  
{  
//竟然溢出了！！  
if (vertices[arc->adjvex].key > vertices[arc->source].key + arc->weight)  
{  
vertices[arc->adjvex].key = vertices[arc->source].key + arc->weight;  
vertices[arc->adjvex].p = &vertices[arc->source];  
}  
}  
//BellmanFord, index為實際第幾個點  
bool BellmanFord(int index)  
{  
InitalizeSingleSource(index-1);  
for (int i = 1; i < vexnum; i++)     //循環共進行vexnum-1次  
{  
//遍曆所有的邊，并對每個邊進行一次松弛  
for (int j = 0; j < vexnum; j++)  
{  
for (ArcNode *arc = vertices[j].firstarc; arc != NULL; arc = arc->nextarc)  
relax(arc);  
}  
}  
//再次遍曆所有的邊，檢查圖中是否存在權重為負值的環路，如果存在，則返回false  
for (int j = 0; j < vexnum; j++)  
{  
for (ArcNode *arc = vertices[0].firstarc; arc != NULL; arc = arc->nextarc)  
{  
if (vertices[arc->adjvex].key > vertices[arc->source].key + arc->weight)  
return false;  
}  
}  
cout << "BellmanFord求出的單源最短路徑：" << endl;  
for (int i = 1; i < vexnum; i++)  
{  
printPath(index-1, i);  
}  
cout << "**************************************************" << endl;  
return true;  
}  
void Dijkstra(int index)  
{  
InitalizeSingleSource(index-1);  
vector snode;       //保存已經找到最短路徑的結點  
vector que;       //保存結點的指針的數組，用這個數組執行堆的算法  
//将結點指針進隊列，形成以key為關鍵值的最小堆  
for (int i = 0; i < vexnum; i++)  
que.push_back(&(vertices[i]));  
//使que按照pvnodecompare準則構成一個最小堆  
make_heap(que.begin(), que.end(), PVNodeCompare());     
while (que.empty() == false)  
{  
//将隊列中擁有最小key的結點出隊  
VNode *node = que.front();  
pop_heap(que.begin(), que.end(), PVNodeCompare());   //從堆中删除最小的結點，隻是放到了vector的最後  
que.pop_back();      //将vector中的這個結點徹底删除，因為後面還要再排序一次，以免影響後面的堆排序，pop算法。  
snode.push_back(*node);  
for (ArcNode *arc = node->firstarc; arc != NULL; arc = arc->nextarc)  
relax(arc);  
make_heap(que.begin(), que.end(), PVNodeCompare());  
}  
cout << "Dijkstra求出的單源最短路徑：" << endl;  
for (int i = 1; i < vexnum; i++)  
{  
if (i != index-1)  
printPath(index-1, i);  
}  
cout << "**************************************************" << endl;  
}  
protected:  
//插入一個表結點  
void insertArc(int vHead, int vTail, int weight)  
{  
//構造一個表結點  
ArcNode *newArcNode = new ArcNode;  
newArcNode->source = vHead;  
newArcNode->adjvex = vTail;  
newArcNode->nextarc = NULL;  
newArcNode->weight = weight;  
//arcNode 是vertics[vHead]的鄰接表  
ArcNode *arcNode = vertices[vHead].firstarc;  
if (arcNode == NULL)  
vertices[vHead].firstarc = newArcNode;  
else  
{  
while (arcNode->nextarc != NULL)  
{  
arcNode = arcNode->nextarc;        
}  
arcNode->nextarc = newArcNode;  
}  
arcnum++;  
vertices[vTail].indegree++;         //對弧的尾結點的入度加1  
}  
//打印源節點到i的最短路徑  
void printPath(int i, int j)  
{  
cout << "從源節點 " << vertices[i].data << " 到目的結點 "  
<< vertices[j].data << " 的最短路徑是：" /*<< endl*/;  
__printPath(&vertices[i], &vertices[j]);  
cout << " 權重為：" << vertices[j].key << endl;  
}  
void __printPath(VNode* source, VNode* dest)  
{  
if (source == dest)  
cout << source->data << "->";  
else if (dest->p == NULL)  
cout << " no path！" << endl;  
else  
{  
__printPath(source, dest->p);  
cout << dest->data << "->";  
}  
}  
private:  
//const數據成員必須在構造函數裡初始化  
static const int MAX_VERTEX_NUM = 20;  //最大頂點個數  
VNode vertices[MAX_VERTEX_NUM];      //存放結點的數組  
int vexnum;             //圖的當前頂點數  
int arcnum;             //圖的弧數  
};  

轉載于:https://my.oschina.net/piorcn/blog/824353

版權聲明：本文内容由互聯網用戶自發貢獻，該文觀點僅代表作者本人。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如發現本站有涉嫌侵權/違法違規的内容， 請發送郵件至 舉報，一經查實，本站将立刻删除。

發布者：全棧程序員棧長，轉載請注明出處：https://javaforall.cn/200706.html原文鍊接：https://javaforall.cn

原文地址：https://cloud.tencent.com/developer/article/2150122