图论_最短路_dij_邻接矩阵.cpp

一些ACM基本算法的测试源码

#include<iostream>
using namespace std;

const int SIZE = 201;
const int INF = 1000000000; 

int n;
int dist[SIZE];
int graph[SIZE][SIZE];
bool visit[SIZE];
//顶点坐标从0开始 
void Dijkstra(int s)//从点s到其它各点的最短距离，保存在数组dist中 
{
    int i, j, minvalue, tmp;
    for(i = 0; i < n; i ++)
    {
        visit[i] = false;
        dist[i] = INF;        
    }     
    dist[s] = 0;
    for(i = 0; i < n; i ++)
    {
        minvalue = INF;
        for(j = 0; j < n; j ++)
            if(!visit[j] && minvalue > dist[j])
            {
                minvalue = dist[j];
                tmp = j;            
            }        
        visit[tmp] = true;
        for(j = 0; j < n; j ++)
            if(!visit[j] && dist[j] > dist[tmp] + graph[tmp][j])
                dist[j] = dist[tmp] + graph[tmp][j];
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            scanf("%d", &graph[i][j]);
    Dijkstra(0);    
    for(int i = 0; i < n; i ++)
        printf("%d\n", dist[i]);
    system("pause");
    return 0;
}

/*
3
0 2 4
2 0 1
4 1 0
*/