# Dijstra算法，求单流最短路径(包含路径)

www.MyException.Cn  网友分享于：2015-08-24  浏览：0次
Dijstra算法，求单源最短路径(包含路径)

dijstra_sample.txt

5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60

```#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

int dist[maxnum];     // 表示当前点到源点的最短路径长度
int pre[maxnum];     // 记录当前点的前一个结点
int cost[maxnum][maxnum];   // 记录图的两点间路径长度
bool vistied[maxnum];

void Dijkstra(int n, int v0)
{
memset(pre,0,sizeof(pre));
memset(vistied, 0, sizeof(<span style="font-family: Arial, Helvetica, sans-serif;">vistied</span><span style="font-family: Arial, Helvetica, sans-serif;">));</span>
for (int i = 1; i <= n; i++)
{
dist[i] = cost[v0][i];
if (dist[i] == maxint)
{
pre[i] = 0;
}
else
pre[i] = 1;
}

vistied[v0] = true;
dist[v0] = 0;
//循环n-1次
for (int i = 2; i <= n; i++)
{
int min = maxint;
int u;
for (int j = 1; j <= n; j++)
{
if (!vistied[j] && min>dist[j])
{
min = dist[j];
u = j;

}
}
vistied[u] = true;
//更新dist
for (int j = 1; j <= n; j++)
{
if (!vistied[j] && min + cost[u][j] < dist[j])
{
dist[j] = min + cost[u][j];
pre[j] = u;
}
}
}
}

void searchPath(int u, int v)
{
int path[maxnum];
memset(path,0,sizeof(path));
int index = 1;
path[index++] = v;
int tmp = pre[v];
while (tmp != u)
{
path[index++] = tmp;
tmp = pre[tmp];
}
path[index] = u;
for (int i = index; i >= 1; i--)
{
cout << path[i] << " ";
}
}

int main()
{
freopen("dijstra_sample.txt", "r", stdin);
// 各数组都从下标1开始

int n, line;             // 图的结点数和路径数

// 输入结点数
cin >> n;
// 输入路径数
cin >> line;
int p, q, len;          // 输入p, q两点及其路径长度

// 初始化c[][]为maxint
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cost[i][j] = maxint;

for (int i = 1; i <= line; ++i)
{
cin >> p >> q >> len;
if (len < cost[p][q])       // 有重边
{
cost[p][q] = len;      // p指向q
cost[q][p] = len;      // q指向p，这样表示无向图
}
}

for (int i = 1; i <= n; ++i)
dist[i] = maxint;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
printf("%8d", cost[i][j]);
printf("\n");
}

Dijkstra(n, 1);

// 最短路径长度
cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;

// 路径
cout << "源点到最后一个顶点的路径为: ";
searchPath(1, n);
}```