最短路：迪杰斯特拉算法

谁借莪１个温暖的怀抱￠ 2021-12-09 06:43 391阅读 0赞

## 迪杰斯特拉算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_5_color_FFFFFF_t_70]  
**伪代码**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]

> 这里是引用

#include<queue>
    #include<stack>
    #include<vector>
    #include<string>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    const int LEN = 7;
    const int inf = INT_MAX;
    int Graph[LEN][LEN] =
    { {-1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, 10, -1, 30, 100},
    {-1, -1, -1, 5,  -1, -1, -1},
    {-1, -1, -1, -1, 50, -1, -1},
    {-1, -1, -1, -1, -1, -1, 10},
    {-1, -1, -1, -1, 20, -1, 60},
    {-1, -1, -1, -1, -1, -1, -1} };
    int crateGraph()
    {
    	for (int i = 1; i < LEN; i++)
    	{
    		for (int j = 0; j < LEN; j++)
    		{
    			if (Graph[i][j] == -1)
    				Graph[i][j] = INT_MAX;
    			if(i == j)
    				Graph[i][j] = 0;
    		}
    	}
    	return 0;
    }
    
    int print(void)
    {
    	for (int i = 1; i < LEN; i++)
    	{
    		for (int j = 1; j < LEN; j++)
    		{
    			if(Graph[i][j] != INT_MAX)
    				cout << Graph[i][j] << " ";
    			else
    				cout <<"∞" << " ";
    		}
    		cout << endl;
    	}
    	return 0;
    }
    int Dijkstra(int s)
    {
    
    	string path[LEN];
    	int dist[LEN] = {0};
    	int visit[LEN] = {0};
    	 
    	visit[s] = 1;
    	
    	for (int i = 1; i < LEN; i++)
    	{
    		dist[i] = Graph[s][i];
    		path[i] = "V" + to_string(s) + "->V" + to_string(i);
    	}
    		
    	for (int i = 1; i < LEN - 1; i++)
    	{
    		int min = inf, w = -1;
    		for (int k = 1; k < LEN; k++)
    		{
    			if (!visit[k] && dist[k] < min)
    				min = dist[w = k];
    		}
    		if (w == -1)
    			break;
    		visit[w] = 1;
    		for (int k = 1; k < LEN; k++)
    		{
    			if (!visit[k] && Graph[w][k] != INT_MAX && dist[k] > dist[w] + Graph[w][k])
    			{
    				dist[k] = dist[w] + Graph[w][k];
    				path[k] = path[w] + "->V" + to_string(k);
    			}
    		}
    	}
    	for (int i = 1; i < LEN; i++)
    	{
    		if(dist[i] != INT_MAX)
    			cout << path[i] << " = " << dist[i] << endl;
    		else
    			cout << path[i] << " = " << "∞" << endl;
    	}
    	return 0;
    }
    int main()
    {
    	int start = 1;
    	crateGraph();
    	print();
    	Dijkstra(start);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_5_color_FFFFFF_t_70]: /images/20211208/0c92034c6b304afdadbe41489c381d9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211208/480eac7ac08e480b8eff09a9ae5a4d83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70 1]: /images/20211208/b8b287b3b0e443cfa8080e960f378344.png