用C++求dijkstra算法求最短路径

来源:百度知道 编辑:UC知道 时间:2024/05/19 20:21:09
问题描述:从键盘上输入一个图的基本信息(图用邻矩阵表示)
1)首先输入图的结点数->num
2)依次输入图的各条边
3)程序所能达到的功能:输出用dijkstra算法求出的一条最短路径。

/**************************************************************
* 给定一个带权有向图G = (V,E),其中每条边的权是一个非负整数。*
* 另外还给定V中的一个顶点,称为源。现在我们要计算从源到所有其 *
* 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问 *
* 题通常称为单源最短路径问题。 *
***************************************************************/
#include<iostream.h>

#define INFINITE 100

void main()
{
int j,i,n,k,t,**w,*s,*p,*d;

cout<<"input the value of n:";
cin>>n;
cout<<endl;

d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];

for(i = 0; i < n; i++)
{
w[i] = new int[n];
}

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)