算法實現(xiàn)思路：
Dijkstra算法
預(yù)處理：將所有的節(jié)點除開始節(jié)點的訪問位置為零表示沒有找到大該節(jié)點的最短路徑，用一個初始化為無窮大的距離數(shù)組存放到已經(jīng)找到節(jié)點到未找到節(jié)點的距離的最小值颗圣，具體為：剛開始時候存放起始節(jié)點到其相鄰節(jié)點的距離值，若節(jié)點不可達則記為無窮大，后續(xù)每次找到一個節(jié)點開始修改這個數(shù)組中的值，看看經(jīng)過這個節(jié)點中轉(zhuǎn)到達其余節(jié)點距離是不是更小焕济，修改節(jié)點的時候順便記錄修改前的前驅(qū)節(jié)點，這樣方便最后輸出找到的路徑盔几。每一次找到節(jié)點就修改距離數(shù)組中的值晴弃，再找距離數(shù)組中的最小的值，將最小值對應(yīng)的節(jié)點的訪問為置為一表示找到該節(jié)點的最短路徑，如此循環(huán)
bellmen_ford算法的實現(xiàn)思路：
第一上鞠，初始化所有點际邻。每一個點保存一個值，表示從原點到達這個點的距離芍阎，將原點的值設(shè)為0世曾，其它的點的值設(shè)為無窮大（表示不可達）。
第二谴咸，進行循環(huán)轮听，循環(huán)下標(biāo)為從1到n－1（n等于圖中點的個數(shù)）。在循環(huán)內(nèi)部岭佳，遍歷所有的邊血巍，進行松弛計算。
算法實現(xiàn)：
# include <stdio.h>
#define INFINITY 9999
#define MAX 10
typedef struct Edge {
int s;
int e;
int v;
}Edge;
Bellman_ford算法實現(xiàn)：
void bellmen_ford(Edge edge[MAX], int vnum, int edgenum, int startnode)
{
int dist[MAX];
int pred[MAX];
int i, j;
// 第一步初始化
for (int i = 0; i < vnum; i++)
{
dist[i] = INFINITY;
pred[i] = startnode;
}
dist[startnode] = 0;
for (int k = 0; k < vnum - 1; k++)//循環(huán)k-1次
{
for (int i = 0; i < edgenum; i++)//循環(huán)每條邊
{
if (dist[edge[i].e] > dist[edge[i].s] + edge[i].v)
{//如果起點 s 的距離加上邊的權(quán)值 v 小于終點 e 的距離珊随，則更新終點 e 的距離值 d
dist[edge[i].e] = dist[edge[i].s] + edge[i].v;
pred[edge[i].e] = edge[i].s;//到e點經(jīng)過s點
}
}
}
for (int i = 0; i < vnum; i++)
if (i != startnode)
{
if (dist[i] == INFINITY)
printf("\n到達V[%d]節(jié)點的路徑長度 = ∞", i);
else
printf("\n到達V[%d]節(jié)點的路徑長度 = %d", i, dist[i]);
if (dist[i] != INFINITY)
{
printf("\n路徑 : V[%d]", i);
j = i;
do
{
j = pred[j];
printf(" <<<< V[%d]", j);
} while (j != startnode);
}
else
{
printf("\n終點不可達");
}
printf("\n");
}
}
Dijikstra算法實現(xiàn)：
void dijikstra(int G[MAX][MAX], int n, int startnode)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i, j;
//對鄰接矩陣進行初步的處理述寡，將0變成無窮大
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (G[i][j] == 0)
cost[i][j] = INFINITY;
else
cost[i][j] = G[i][j];
//初始化距離數(shù)組
for (i = 0; i < n; i++)
{
distance[i] = cost[startnode][i];
pred[i] = startnode;
visited[i] = 0;
}
distance[startnode] = 0;
visited[startnode] = 1;
count = 1;
while (count < n - 1)
{
mindistance = INFINITY;
for (i = 0; i < n; i++)//找到相鄰的最小距離的哪個節(jié)點
if (distance[i] < mindistance && !visited[i])
{
mindistance = distance[i];
nextnode = i;
}
visited[nextnode] = 1;
for (i = 0; i < n; i++)//修改存放最小距離的數(shù)組并修改前驅(qū)
if (!visited[i])
if (mindistance + cost[nextnode][i] < distance[i]) {
distance[i] = mindistance + cost[nextnode][i];
pred[i] = nextnode;
}
count++;
}
//輸出路徑
for (i = 0; i < n; i++)
if (i != startnode)
{
if (distance[i] == INFINITY)
printf("\n到達V[%d]節(jié)點的路徑長度 = ∞", i);
else
printf("\n到達V[%d]節(jié)點的路徑長度 = %d", i, distance[i]);
if (distance[i] != INFINITY)
{
printf("\n路徑 : V[%d]", i);
j = i;
do
{
j = pred[j];
printf(" <<<< V[%d]", j);
} while (j != startnode);
}
else
{
printf("\n終點不可達");
}
printf("\n");
}
}
主函數(shù)：
int main()
{
int vnum, edgenum, startnode;
int G[MAX][MAX];
int start, end, value;
Edge edge[MAX];
printf("輸入圖的 頂點數(shù) 和 邊數(shù)：");
scanf("%d %d", &vnum, &edgenum);
for (int i = 0; i < vnum; i++)
for (int j = 0; j < vnum; j++)
{
if (i == j)
G[i][j] = 0;
else
G[i][j] = INFINITY;
}
printf("輸入每條變的 起點 終點 以及其 權(quán)重:\n");
for (int k = 0; k < edgenum; k++)
{
printf("(%d): ", k + 1);
scanf("%d %d %d", &start, &end, &value);
printf("\n");
G[start][end] = value;
edge[k].s = start;
edge[k].e = end;
edge[k].v = value;
}
printf("鄰接矩陣是：\n");
for (int i = 0; i < vnum; i++)
{
for (int j = 0; j < vnum; j++)
{
if (G[i][j] == INFINITY)
printf("∞\t");
else
printf("%d\t", G[i][j]);
}
printf("\n");
}
printf("\n輸入起始的頂點\t");
scanf("%d", &startnode);
printf("\n##################Dijikstra######################\n");
dijikstra(G, vnum, startnode);
printf("\n################Bellmen_Ford#####################\n");
bellmen_ford(edge, vnum, edgenum, startnode);
system("pause");
}
輸入：
輸入?yún)?shù)
輸出鄰接矩陣：
鄰接矩陣
開始輸入起始節(jié)點：
這里選擇將零作為起始節(jié)點
輸出結(jié)果：
輸出結(jié)果
將所有代碼拷到一個文件中就可以運行
