Programming problems related to C++ Dijkstra algorithm

#include<iostream>
using namespace std;
#define N 10000
#define Linit 11

void Dijstra(int edges[][Linit], int origin, int* dist, int* path);

int main()
{
	char str[200] = {'1','-','4',',','1','-','6',',','2','-','4',',','2','-','6',',','3','-','5',',','3','-','6',',','4','-','5',',','5','-','6'};
	int origin = 1;
	int target = 3;

	int dist[Linit] = { N };	//The shortest path length from the original node to each Vi endpoint
	int path[Linit] = { -1 };	//Save the previous node of Vi on the shortest path from the original node to the node Vi
	int edges[Linit][Linit];		//adjacency matrix
	//int node_num = 0; 				// Number of nodes in the graph
	int x = 0, y = 0;


	for (int i = 0; i < Linit; i++)
	{
		for (int j = 0; j < Linit; j++)
		{
			if (i == j)
			{
				edges[i][j] = 0;
			}
			else
			{
				edges[i][j] = N;
			}

		}
	}

	/*cout << "Origin and destination: "<< endl;
	cin >> origin >> target;
	cout << "Please enter a vertex-vertex string: "<< endl;
	cin >> str;*/

	cout << origin << "to" << target << ":" << str << endl;

	//edges[][] initialization
	for (int i = 0; str[i] != '\0'; i += 4)
	{
		x = str[i] - '0';
		y = str[i + 2] - '0';
		edges[x][y] = 1;
		edges[y][x] = 1;
		//cout << "x=" << x  <<  "y= " << y << endl;
	}


	Dijstra(edges, origin, dist, path);

	cout << target << " ";
	for (int i = target; path[i] != origin; i = path[i])
	{
		cout << path[i] << " ";
	}
	cout << origin << endl;
	return 0;
}

void Dijstra(int edges[][Linit], int origin, int* dist, int* path)
{
	int set[N]; //t[i] == 1, indicating that the node is included in the shortest path set
		int min, i, j, u;

	//Initialization
	
	for (int i = 0; i < Linit; i++)
	{
		//dist[] initialization
		dist[i] = edges[origin][i];
		set[i] = 0;
		//path[] initialization

		if (edges[origin][i] < N && i != origin)
		{
			path[i] = origin;
		}
		else
		{
			path[i] = -1;
		}
	}

	set[origin] = 1;
	path[origin] = -1;

	//Start of critical operation
	for (i = 1; i < Linit; i++)
	{
		min = N;
		for (j = 1; j < Linit; j++) 
		{
			if (set[j] == 0 && dist[j] < min)
			{
				u = j;
				min = dist[j];
			}
		}
		set[u] = 1; //Merge the selected vertices into the shortest path

		for (j = 1; j < Linit; j++)
		{
			if (set[j] == 0 && dist[u] + edges[u][j] < dist[j])
			{
				dist[j] = dist[u] + edges[u][j];
				path[j] = u;
			}
		}
	}
}

Output results:

Reference to High Score Notes on Data Structure

Welcome to Markdown Editor

Hello! This is the first welcome page you've shown using the Markdown editor. If you want to learn how to use the Markdown editor, you can read this article carefully to learn the basic grammar of Markdown.

New Changes

We've expanded the functionality and grammar support of the Markdown editor. In addition to the standard Markdown editor functionality, we've added the following new features to help you blog with it:

  1. A new interface design will bring a new writing experience.
  2. Set up your favorite code highlighting style in the authoring center, and Markdown displays the selected highlighting style for the code snippet display.
  3. Added drag-and-drop function to allow you to drag local pictures directly to the editing area for display.
  4. New KaTeX math formula syntax;
  5. Added mermail syntax to support Gantt chart 1 Functions;
  6. Added multi-screen editing Markdown article function;
  7. Functions such as Focus Writing Mode, Preview Mode, Simple Writing Mode, left and right area synchronization wheel settings have been added. Function buttons are located in the middle of edit area and preview area.
  8. Added checklist function.

Function Shortcuts

Undo: Ctrl/Command + Z
Redo: Ctrl/Command + Y
Bold: Ctrl/Command + B
Italic: Ctrl/Command + I
Title: Ctrl/Command + Shift + H
Unordered list: Ctrl/Command + Shift + U
Ordered list: Ctrl/Command + Shift + O
Checklist: Ctrl/Command + Shift + C
Insert code: Ctrl/Command + Shift + K
Insert link: Ctrl/Command + Shift + L
Insert picture: Ctrl/Command + Shift + G
Find: Ctrl/Command + F
Replace: Ctrl/Command + G

Create titles appropriately to help generate catalogs

Type # once directly and press space to generate a level 1 title.
Enter # twice and press space to generate a level 2 title.
By analogy, we support level 6 titles. Helps generate a perfect directory using TOC syntax.

How to change the style of text

Emphasis Text Emphasis Text

Bold Text Bold Text

Markup Text

Delete Text

Reference Text

H2O is a liquid.

The result of 210 is 1024.

Insert links and pictures

Links: link.

Picture:

Pictures with dimensions:

Centered picture:

Centered and sized picture:

Of course, to make it easier for users, we added drag-and-drop pictures.

How to insert a beautiful snippet of code

go Blog Settings Page, select a code highlight style that you like, and show the same highlighted code below.

// An highlighted block
var foo = 'bar';

Generate a list that works for you

  • project
    • project
      • project
  1. Item 1
  2. Item 2
  3. Item 3
  • Schedule Tasks
  • Complete Task

Create a table

A simple table is created like this:

projectValue
Computer$1600
Mobile phone$12
catheter$1

Set content centered, left, right

Use: ---------: Center
Use: ------------- Left
Use --------: Right

Column 1Column 2Column 3
First column text centeredSecond column text rightLeft text in column 3

SmartyPants

SmartyPants converts ASCII punctuation characters to "smart" printed punctuation HTML entities. For example:

TYPEASCIIHTML
Single backticks'Isn't this fun?''Isn't this fun?'
Quotes"Isn't this fun?""Isn't this fun?"
Dashes-- is en-dash, --- is em-dash– is en-dash, — is em-dash

Create a custom list

Markdown Text-to- HTML conversion tool Authors John Luke

How to create a footer

A text with footnotes. 2

Notes are also essential

Markdown converts text to HTML.

KaTeX Mathematical Formula

You can use Rendering LaTeX Mathematical Expressions KaTeX:

Gamma Formula Display Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N \Gamma(n) = (n-1)!\quad\forall n\in\mathbb N Γ (n)=(n_1)! _n < N is via Euler integral

Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t   . \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=∫0∞​tz−1e−tdt.

You can find more information about LaTeX mathematical expressions here.

New Gantt Chart features to enrich your articles

  • About Gantt Grammar, Reference here,

UML Diagram

You can use UML diagrams for rendering. Mermaid . For example, a sequence diagram is generated below:

This will result in a flowchart.

  • About Mermaid syntax, reference here,

FLowchart Flowchart

We will still support flowchart flowcharts:

  • Reference for Flowchart flowchart syntax here.

Export and Import

export

If you want to try this editor, you can edit it anywhere in this article. When you have finished writing an article, find the article export in the toolbar above and generate one. md file or. The html file is saved locally.

Import

If you want to load an article you've written. md file, in the toolbar above you can choose the import function to import files with corresponding extensions.
Continue with your creation.

  1. mermaid syntax description ↩︎

  2. Explanation of footnotes ↩︎

Tags: C++ Algorithm

Posted by dirkbonenkamp on Sat, 02 Jul 2022 21:45:03 +0300